当前位置：首页 > article >正文

【Swift 算法实战】城市天际线问题解法

article 2025/3/1 9:31:33

在这里插入图片描述

网罗开发 （小红书、快手、视频号同名）

大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：极星会首批签约作者

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 步骤解析
  - Swift 代码实现
- 示例测试及结果
- - 示例 1：
  - 示例 2：
- 时间复杂度与空间复杂度
- 总结
- 参考资料

摘要

城市天际线问题要求根据给定的建筑物位置和高度，计算出从远处看这些建筑物形成的天际线轮廓。每个建筑物都可以用一个三元组 [lefti, righti, heighti] 表示，分别表示建筑物的左边界、右边界和高度。本文将介绍如何使用 Swift 高效地计算天际线，解题过程中会用到优先队列（最大堆）来动态维护当前最大高度，从而生成天际线。

描述

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。

你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行排序。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意： 输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

示例 1：

输入： buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出： [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。

示例 2：

输入： buildings = [[0,2,3],[2,5,3]]
输出： [[0,3],[5,0]]

提示：

1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings 按 lefti 非递减排序

题解答案

天际线问题是一个典型的扫描线问题，我们可以通过以下步骤来解决：

事件建模：首先，将每个建筑物的左端点和右端点视为事件。每个左端点可以看作是一个建筑物的起始位置，需要记录该建筑物的高度；右端点则表示建筑物结束，需要移除该建筑物。
优先队列（最大堆）：利用优先队列（最大堆）来动态维护当前活跃的建筑物的高度。每当遇到左端点时，将建筑物的高度加入堆中；当遇到右端点时，将建筑物的高度从堆中移除。
生成关键点：通过扫描事件点，我们根据当前堆的最大高度来确定天际线的高度。每当堆的最大值发生变化时，记录下新的关键点。

题解代码分析

步骤解析

事件构建：将每个建筑物的左端点和右端点作为事件，分别表示建筑物的开始和结束。对于每个事件，我们需要记录其横坐标、事件类型（左端点或右端点）和高度。
优先队列：使用最大堆来维护当前的建筑物高度，堆的根节点即为当前活跃建筑物的最大高度。
遍历并生成结果：按横坐标排序所有事件，遍历事件时，动态维护堆，生成天际线的关键点。

Swift 代码实现

import Foundation

func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
    var events = [(x: Int, h: Int, type: Int)]()
    for building in buildings {
        let (left, right, height) = (building[0], building[1], building[2])
        events.append((x: left, h: height, type: 1))  // 左端点事件
        events.append((x: right, h: height, type: -1)) // 右端点事件
    }

    // 按照横坐标排序，横坐标相同的事件按类型排序（左端点优先）
    events.sort { $0.x < $1.x || ($0.x == $1.x && $0.type > $1.type) }

    var result = [[Int]]()
    var maxHeap = [(h: Int, count: Int)]() // (高度, 数量)，maxHeap 以高度为优先级，模拟最大堆
    var heightToCount = [Int: Int]() // 高度到数量的映射

    for event in events {
        let (x, h, type) = event

        if type == 1 { // 左端点
            heightToCount[h, default: 0] += 1
        } else { // 右端点
            heightToCount[h, default: 0] -= 1
        }

        // 更新堆
        var currentHeight = 0
        for (key, value) in heightToCount {
            if value > 0 {
                currentHeight = max(currentHeight, key)
            }
        }

        if result.isEmpty || result.last![1] != currentHeight {
            result.append([x, currentHeight])
        }
    }

    return result
}

示例测试及结果

示例 1：

let buildings1 = [[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]
print(getSkyline(buildings1)) 
// 输出: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

示例 2：

let buildings2 = [[0, 2, 3], [2, 5, 3]]
print(getSkyline(buildings2))
// 输出: [[0, 3], [5, 0]]

时间复杂度与空间复杂度

时间复杂度：O(n log n)
排序事件需要 O(n log n) 时间，堆操作也需要 O(log n) 时间，整体复杂度为 O(n log n)，其中 n 是建筑物的数量。
空间复杂度：O(n)
存储事件和堆需要 O(n) 的空间，n 为建筑物的数量。