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

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

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

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

摘要

城市天际线问题要求根据给定的建筑物位置和高度，计算出从远处看这些建筑物形成的天际线轮廓。每个建筑物都可以用一个三元组 [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 非递减排序

题解答案

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

1. 事件建模：首先，将每个建筑物的左端点和右端点视为事件。每个左端点可以看作是一个建筑物的起始位置，需要记录该建筑物的高度；右端点则表示建筑物结束，需要移除该建筑物。

2. 优先队列（最大堆）：利用优先队列（最大堆）来动态维护当前活跃的建筑物的高度。每当遇到左端点时，将建筑物的高度加入堆中；当遇到右端点时，将建筑物的高度从堆中移除。

3. 生成关键点：通过扫描事件点，我们根据当前堆的最大高度来确定天际线的高度。每当堆的最大值发生变化时，记录下新的关键点。

题解代码分析

步骤解析

1. 事件构建：将每个建筑物的左端点和右端点作为事件，分别表示建筑物的开始和结束。对于每个事件，我们需要记录其横坐标、事件类型（左端点或右端点）和高度。

2. 优先队列：使用最大堆来维护当前的建筑物高度，堆的根节点即为当前活跃建筑物的最大高度。

3. 遍历并生成结果：按横坐标排序所有事件，遍历事件时，动态维护堆，生成天际线的关键点。

Swift 代码实现

import Foundationfunc 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) = eventif type == 1 { // 左端点heightToCount[h, default: 0] += 1} else { // 右端点heightToCount[h, default: 0] -= 1}// 更新堆var currentHeight = 0for (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 为建筑物的数量。

总结

通过扫描线算法并结合最大堆数据结构，我们可以高效地计算出由多个建筑物形成的城市天际线。对于每个建筑物的左端点和右端点事件，我们利用最大堆来维护当前最大高度，并根据高度变化生成关键点。最终我们得到了天际线的正确轮廓。

这种算法不仅能高效地处理较大规模的输入数据，还能保证输出的正确性。随着建筑物数量和坐标范围的增大，这种解法的优势更加突出。

参考资料

• LeetCode 题目解答：Skyline Problem
• Swift 官方文档
• 扫描线算法