LeetCode 218. 天际线问题
目录
题目描述
题意分析
给定若干矩形建筑，每个用
[left, right, height]描述，它们从地面长起、可以任意重叠。要求输出这些建筑叠加后从远处看到的外轮廓，用一串「关键点」[x, y]表示：每个关键点意味着轮廓高度在横坐标x处变成了y。相邻关键点之间高度恒定，最后一个关键点的y必须是 0。「轮廓」这个词翻译成可计算的定义是：对任意横坐标
x，轮廓高度等于所有覆盖x的建筑中的最大高度，没有建筑覆盖时为 0。所以本质上要刻画的是一个从左到右的分段常值函数，而输出只保留函数值发生跳变的位置。这个定义直接给出两条硬性要求。其一，同一个横坐标上不能输出两个关键点——若多栋建筑恰好在同一个
x处同时开始和结束，中间过程哪怕高度反复变化，最终也只该记录这一处的最终高度。其二，高度没变就不能输出——两栋等高建筑首尾相接时，交界处轮廓是平的，不产生关键点。数据规模上限在 $10^4$ 量级而坐标可以取到 $2^{31}$，说明不能按坐标建数组，只能按事件离散化处理；同时 $O(n^2)$ 的两两比较也在可承受边缘之外，需要 $O(n \log n)$ 的方案。
还有一处细节容易被忽略：建筑的右端点是开区间。建筑
[1, 3, 4]覆盖的是 $[1, 3)$，在x = 3这一点它已经不再贡献高度。这决定了左端点事件和右端点事件在同一坐标相遇时的处理必须小心。边界：只有一栋建筑时输出两个点，左端点升到
height、右端点降到 0；建筑完全被另一栋更高更宽的建筑包住时，它不产生任何关键点。
解法：扫描线 + 高度多重集合
核心思路
暴力做法是把所有端点坐标收集起来排序，对每个坐标遍历全部建筑求覆盖它的最大高度。这确实能算对，但每个坐标都要扫一遍建筑，是 $O(n^2)$。瓶颈很清楚：相邻两个坐标之间，覆盖情况只变了几栋建筑，却把全部建筑重新算了一遍。
由此得到关键观察：把视线看成一条从左往右移动的竖直扫描线，建筑对它的影响只在两个时刻发生变化——扫描线越过左端点时这栋建筑「进入」，越过右端点时「离开」。中间的所有位置，覆盖集合完全不变，自然也不会产生关键点。所以只需要在这 $2n$ 个「事件」处停下来更新，而不是在每个坐标处重算。
于是把每栋建筑
[l, r, h]拆成两个事件：(l, -h)表示加入高度h，(r, h)表示移除高度h。事件只需按横坐标排序；同一x的事件会全部处理完再读取最高高度，所以组内先后不影响结果。活跃高度结构要支持插入、删除指定高度和查询最大值，而且重复高度必须分别计数。Java 用
TreeMap<高度, 次数>；Go 用标准库大顶堆配合计数表惰性删除：结束事件只减计数，读取最大值前持续弹出计数为 0 的堆顶。循环不变量可以显式写成：在处理完横坐标
x处的全部事件之后，多重集合恰好等于「所有覆盖区间包含x的建筑高度」的集合（外加一个哨兵 0），prevHeight等于上一个已输出关键点的高度。集合里预置一个 0 是为了让「没有任何建筑覆盖」时lastKey()仍有值可取，省掉空集判断。有了这个不变量，产生关键点的判据就是一句话：处理完
x的全部事件后，若集合最大值不等于prevHeight，就输出[x, 最大值]并更新prevHeight。而「处理完x的全部事件」这个前提，正是靠内层while把同一坐标的事件一次性吃掉来保证的——这也直接满足了题意分析里「同一坐标只输出一个点」的要求。右端点开区间的语义也被这套写法自动照顾到了：建筑
[1, 3, 4]的移除事件在x = 3处，处理完之后集合里已经没有高度 4，所以x = 3处算出的高度不含它，正是 $[1, 3)$ 的语义。而若另一栋建筑[3, 5, 4]恰好从 3 开始，它的加入事件与前者的移除事件在同一坐标批处理，一加一减后最大高度不变，于是不输出关键点——两栋等高建筑首尾相接被正确地看成一段连续平顶。
解题步骤
- 拆事件：对每栋建筑生成
(left, -height)与(right, height)，符号只负责区分加入和移除。- 排序：只按横坐标升序。同坐标事件必须批量处理，因此组内顺序无需承担正确性；这比依赖复杂的起终点排序规则更稳。
- 初始化多重集合放入哨兵 0：为什么要这个 0——它代表「地面」，保证任何时刻集合非空，
lastKey()不会抛异常；同时地面高度 0 也确实是轮廓在无建筑处的真实取值。- 外层循环取出当前坐标
x，内层while把所有横坐标等于x的事件全部处理完：负值表示加入，把-height的计数加一；正值表示移除，把该高度计数减一，减到 0 时从集合里删除键。为什么必须批处理——若逐条事件就判断一次，同一坐标上的中间态会被当成真实高度输出，产生重复横坐标的关键点。- 批处理结束后取最大高度并比较：若
curHeight != prevHeight就把[x, curHeight]加入答案并更新prevHeight。为什么用「变了才输出」而不是无条件输出——这正是题意里「相邻关键点高度必须不同」的约束，等高相接、被完全覆盖的建筑都靠这一句被过滤掉。- 返回答案：不需要额外收尾。最后一个事件必然是某栋建筑的移除，处理完后集合只剩哨兵 0，最大高度为 0，与之前的非零
prevHeight不同，因此自动输出了以 0 结尾的关键点。以
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]走一遍。拆出 10 条事件，按横坐标依次位于 2、3、5、7、9、12、15、19、20、24。集合初值
{0:1}，prevHeight = 0。
x=2：加入 10，集合{0,10}，最大 10 ≠ 0，输出[2,10]，prevHeight=10。
x=3：加入 15，集合{0,10,15}，最大 15 ≠ 10，输出[3,15]，prevHeight=15。
x=5：加入 12，集合{0,10,12,15}，最大仍是 15，等于prevHeight，不输出——这正是「新建筑被更高的建筑挡住」的情形。
x=7：移除 15，集合{0,10,12}，最大 12 ≠ 15，输出[7,12]，prevHeight=12。
x=9：移除 10，集合{0,12}，最大仍是 12，不输出——被移除的不是当前最高者，轮廓没变。
x=12：移除 12，集合{0}，最大 0 ≠ 12，输出[12,0]，prevHeight=0。
x=15：加入 10，集合{0,10}，输出[15,10]，prevHeight=10。
x=19：加入 8，集合{0,8,10}，最大仍是 10，不输出。
x=20：移除 10，集合{0,8}，最大 8 ≠ 10，输出[20,8]，prevHeight=8。
x=24：移除 8，集合{0}，最大 0 ≠ 8，输出[24,0]。最终答案
[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]，与标准输出一致。再用
[[1,3,4],[3,5,4]]验证批处理。x=3同时有一个高度 4 结束、另一个高度 4 开始；无论组内先处理哪一个，整组结束后的有效计数仍为 1，最高高度仍是 4，因此不能输出新点。最终答案是[[1,4],[5,0]]。若逐条事件就判断高度，先移除时会泄漏中间态，错误输出[3,0]和[3,4]。
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;
// 同一个 x 上必须合并处理所有事件，再统一判断最高高度是否变化，避免同一坐标输出多个关键点。
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
int[][] events = new int[buildings.length * 2][2];
int index = 0;
for (int[] building : buildings) {
events[index++] = new int[]{building[0], -building[2]};
events[index++] = new int[]{building[1], building[2]};
}
Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
TreeMap<Integer, Integer> heightCount = new TreeMap<>();
heightCount.put(0, 1);
List<List<Integer>> res = new ArrayList<>();
int i = 0;
int prevHeight = 0;
while (i < events.length) {
int x = events[i][0];
while (i < events.length && events[i][0] == x) {
int height = events[i][1];
if (height < 0) {
int actualHeight = -height;
heightCount.put(actualHeight, heightCount.getOrDefault(actualHeight, 0) + 1);
} else {
int count = heightCount.get(height);
if (count == 1) {
heightCount.remove(height);
} else {
heightCount.put(height, count - 1);
}
}
i++;
}
int curHeight = heightCount.lastKey();
if (curHeight != prevHeight) {
res.add(Arrays.asList(x, curHeight));
prevHeight = curHeight;
}
}
return res;
}
}
import (
"container/heap"
"sort"
)
type maxHeap []int
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(value any) {
*h = append(*h, value.(int))
}
func (h *maxHeap) Pop() any {
old := *h
value := old[len(old)-1]
*h = old[:len(old)-1]
return value
}
// 同一个 x 上必须合并处理所有事件，再统一判断最高高度是否变化，避免同一坐标输出多个关键点。
func getSkyline(buildings [][]int) [][]int {
events := make([][2]int, 0, len(buildings)*2)
for _, building := range buildings {
events = append(events, [2]int{building[0], -building[2]})
events = append(events, [2]int{building[1], building[2]})
}
sort.Slice(events, func(i, j int) bool {
return events[i][0] < events[j][0]
})
heightCount := map[int]int{0: 1}
heights := &maxHeap{0}
heap.Init(heights)
result := make([][]int, 0)
previousHeight := 0
for i := 0; i < len(events); {
x := events[i][0]
for i < len(events) && events[i][0] == x {
height := events[i][1]
if height < 0 {
height = -height
heightCount[height]++
heap.Push(heights, height)
} else {
heightCount[height]--
}
i++
}
for heightCount[(*heights)[0]] == 0 {
heap.Pop(heights)
}
currentHeight := (*heights)[0]
if currentHeight != previousHeight {
result = append(result, []int{x, currentHeight})
previousHeight = currentHeight
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n \log n)$。排序 $2n$ 个事件是 $O(n \log n)$；Java 每次多重集合更新为 $O(\log n)$，Go 中每个高度至多入堆一次、出堆一次，惰性清理的总成本同样为 $O(n \log n)$。
- 空间复杂度：$O(n)$，事件、活跃高度结构和最多 $2n$ 个关键点均为线性规模。
关键点总结
- 遇到「区间叠加后的整体效果」类问题，先想能否把区间拆成端点事件，把二维的覆盖关系降成一维的时间轴扫描——这是扫描线的通用套路，56、253、1094 都是同一个模子。
- 数据结构要按需要的操作选，而不是按印象选：本题需要「删除指定值 + 查询最大值」，这排除了普通堆（只能删最大）和普通集合（不支持重复），指向多重集合。能当场说清这条排除链，比直接背出
TreeMap更有说服力。- 没有有序容器的语言里，「堆 + 计数表惰性删除」是多重集合的标准替代：删除只记账不动堆，只在读取堆顶时清理失效元素，把删除的代价摊还到读取上。
- 同一坐标的事件必须批量处理后再判断输出，否则中间态会泄漏成答案。凡是「事件在同一时刻并发」的扫描线题，这一步都不能省。
- 在集合里预置一个哨兵 0，把「无建筑覆盖」变成集合里的一个普通元素，消掉了空集特判——用哨兵消除边界分支是链表、单调栈、扫描线共用的技巧。
- 面试表达要讲清两条：普通堆不能删除指定高度，所以需要计数惰性删除；同坐标事件必须先全部更新，才能得到该坐标唯一的最终高度。
易错点总结
- 同一坐标的事件逐条处理而不批量合并：用例
[[1,3,4],[3,5,4]]，若在x=3处先处理移除再判断，会看到最大高度变成 0 而输出[3,0]，接着处理加入又输出[3,4]，答案里出现两个横坐标为 3 的点，直接判错。- 用普通
TreeSet/HashSet而不是多重集合：用例[[1,5,3],[2,4,3]]，两栋等高建筑重叠，x=4处移除高度 3 会把集合里唯一的 3 删光，导致错误输出[4,0]，而正确轮廓到x=5才落地。- 结束事件直接弹堆顶：
[[1,5,10],[2,3,5]]在x=3结束的是高度 5，但堆顶是仍然有效的高度 10；直接弹顶会删错建筑并让轮廓提前下降。- 忘记在集合里预置哨兵 0：用例
[[1,2,3]]，x=2移除后集合为空，lastKey()抛NoSuchElementException（Go 版则是空堆越界 panic），本该输出的收尾点[2,0]永远出不来。- 无条件输出每个事件坐标的高度：用例
[[1,10,5],[2,3,2]]，矮建筑完全被高建筑包住，x=2和x=3处最大高度始终是 5，无条件输出会多出[2,5]、[3,5]两个与前一点等高的冗余关键点。- 同坐标只处理一条事件就读取最高值：
[[1,3,4],[3,5,4]]在x=3同时结束和开始；泄漏任一中间态都会产生重复横坐标。组内顺序可以任意，但必须整组处理后只比较一次。- 误以为右端点是闭区间而把移除事件推迟到
right + 1：用例[[1,3,4],[3,5,4]]的相接会变成重叠，虽然本例答案巧合相同；但用例[[1,3,4],[3,5,9]]会在x=3处仍保留高度 4，虽不影响最大值，而[[1,3,9],[3,5,4]]则会让x=3处仍算出 9，漏掉本该输出的[3,4]。- 建筑坐标可到 $2^{31}-1$ 却按坐标开数组：用例
[[0,2147483647,1]]，试图开长度为坐标范围的高度数组会直接内存溢出，这就是必须走事件离散化而非差分数组的原因。- Java 里移除时直接
heightCount.remove(height)而不判断计数：用例[[1,5,3],[2,4,3]]，x=4处计数应从 2 降到 1，直接remove会把仍然有效的那栋建筑一并抹掉，轮廓提前落地。- Go 版惰性删除后忘记在读堆顶前调用清理：用例
[[1,5,10],[2,3,20]]，x=3只把 20 的计数减到 0 而没弹出，读堆顶仍拿到 20，会错误输出[3,20]之后再也降不下来。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 253. 会议室 II | 中等 | 同样拆端点事件，但只需维护当前重叠数量，用最小堆即可，无需多重集合 |
| 1094. 拼车 | 中等 | 事件带权且坐标范围小，可直接用差分数组求前缀和，是扫描线的数组特化版 |
| 56. 合并区间 | 中等 | 只按左端点排序后线性合并，不需要事件拆分，体现「何时可以不用扫描线」 |
| 57. 插入区间 | 中等 | 输入已有序，考察一次遍历中三段式处理，重点在边界的开闭判断 |
| 1288. 删除被覆盖区间 | 中等 | 靠「左升右降」的排序技巧把覆盖判定降成单变量比较，是排序设计的典型 |
| 732. 我的日程安排表 III | 困难 | 在线版本的最大重叠数，需要动态开点线段树或有序表差分，考察增量维护 |
| 850. 矩形面积 II | 困难 | 扫描线升级到二维求并集面积，需要线段树维护当前被覆盖的纵向长度 |
| 759. 员工空闲时间 | 困难 | 求的是覆盖区间的补集，考察合并后取间隙，与本题「求轮廓」是同一扫描线的两面 |