0218. The Skyline Problem¶
题目信息¶
- 题号:
天际线问题
- 难度:
Hard
- 主题:
扫描线、事件排序、多重集合、轮廓压缩
- 原题:
- 重点:
半开区间、活动建筑、同坐标批处理、最高高度变化
题目重述¶
每座建筑用 [left, right, height] 表示,覆盖半开区间 left <= x < right,高度为正整数;建筑之间可以重叠、包含,
也可以只在边界接触。返回从左到右的外轮廓关键点 [x, height]:在横坐标 x 右侧,轮廓高度发生变化时输出该点,
最后必须回到高度 0;连续保持同一高度的区间不能拆成多个点。建筑数量最多为 10^4,每座建筑保证 left < right。
自建示例¶
两座建筑部分重叠:
buildings = [[2,9,10],[3,7,15],[5,12,12]]
输出 = [[2,10],[3,15],[7,12],[12,0]]
在 x=7,高度 15 的建筑结束,但高度 12 仍覆盖右侧;在 x=12,所有建筑都结束,轮廓回到 0。
同一坐标的接替不能产生零宽度拐点:[[1,3,4],[3,5,4]] 的输出是 [[1,4],[5,0]],
而不是在 x=3 先降到 0 再升回 4。
包含关系也要求保留低楼的结束状态:[[1,10,5],[2,4,8]] 的轮廓为 [[1,5],[2,8],[4,5],[10,0]]。
C++ 实现¶
#include <algorithm>
#include <set>
#include <utility>
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> getSkyline(
std::vector<std::vector<int>>& buildings) {
std::vector<std::pair<int, int>> events;
events.reserve(buildings.size() * 2);
for (const std::vector<int>& building : buildings) {
events.push_back({building[0], -building[2]});
events.push_back({building[1], building[2]});
}
std::sort(events.begin(), events.end());
std::multiset<int> active{0};
std::vector<std::vector<int>> answer;
int previous_height = 0;
std::size_t index = 0;
while (index < events.size()) {
const int x = events[index].first;
while (index < events.size() && events[index].first == x) {
const int encoded = events[index].second;
if (encoded < 0) {
active.insert(-encoded);
} else {
active.erase(active.find(encoded));
}
++index;
}
const int current_height = *active.rbegin();
if (current_height != previous_height) {
answer.push_back({x, current_height});
previous_height = current_height;
}
}
return answer;
}
};
题解¶
从横坐标切片到事件扫描¶
直接做法先收集所有左右边界,把相邻边界切成小段;对每段再扫描全部建筑,找出覆盖该段的最高高度。不同边界最多有 2n 个,
每段都重新检查 n 座建筑,最坏工作量为 O(n^2),而且重复判断了同一座建筑在多个小段上的覆盖关系。
轮廓只可能在建筑开始或结束的位置变化。把一座建筑压缩成两个事件:在 left 加入它的高度,在 right 移除它的高度;
从左到右处理事件后,活动建筑集合就代表从当前坐标到下一个事件坐标之间的全部高度。于是横坐标切片不再主动扫描建筑,
只需维护事件带来的增量。
活动集合与轮廓状态¶
用 active 保存当前覆盖区间内每座建筑的高度,并放入高度 0 哨兵表示没有建筑。处理完同一个坐标 x 的全部事件后,
保持以下状态:
active包含且只包含覆盖右侧开区间[x, next_x)的建筑;*active.rbegin()是该区间的真实轮廓高度;同高度建筑分别占据多重集合中的不同副本,移除一座不会移除另一座;
previous_height是上一个已经输出的轮廓高度。
只有当前最高高度与 previous_height 不同,x 才是关键点。必须先处理完坐标组,再读取最高高度,因为同一坐标内的中间状态
没有正宽度区间;这正是半开区间和批处理顺序在实现中的对应关系。
相邻事件坐标之间没有建筑进出,active 不变,所以最高高度在整个 [x,next_x) 上恒定;记录高度变化的第一个坐标,
就同时覆盖了轮廓的完整性和“连续同高只输出一次”的压缩要求。
事件编码与同坐标处理¶
事件的第二个分量用负数表示开始、正数表示结束,绝对值是建筑高度;这样既用一个 pair 表达两类事件,
又能让排序按坐标排列。相同坐标的事件会被内层循环收成一组,开始事件和结束事件在组内的先后不影响最终高度,
因为代码只在整组更新后读取 active.rbegin()。
对 [[1,3,4],[3,5,4]],处理 x=3 时一份高度 4 被删除、另一份高度 4 被加入。若每个事件后立即输出,集合会短暂出现
{0},但这个状态没有任何宽度;批处理后集合仍含高度 4,和上一段高度相同,因此不产生多余关键点。
事件扫描删除的重复工作¶
直接切片法在每个小段都重新询问“哪些建筑覆盖这里”;事件法把一座建筑的影响拆为一次加入和一次移除,
每个边界只处理发生变化的状态。事件排序负责横坐标顺序,多重集合负责高度顺序,previous_height 负责把连续水平线压成一个关键点。
为什么必须使用多重集合¶
set 只能保存一个高度副本。若两座重叠的建筑高度都为 10,较早结束的那座删除 10 时,普通集合无法知道另一座仍在覆盖,
轮廓会被错误降低;multiset 为每个开始事件保留一份高度。结束事件通过 find 删除其中一份,其他同高建筑仍然存在。
状态走读¶
对 [[2,9,10],[3,7,15],[5,12,12]],处理完每个坐标组后的状态如下:
坐标 |
事件变化 |
|
新高度与输出 |
|---|---|---|---|
2 |
加入 10 |
|
10,输出 |
3 |
加入 15 |
|
15,输出 |
5 |
加入 12 |
|
仍为 15,不输出 |
7 |
移除 15 |
|
12,输出 |
9 |
移除 10 |
|
仍为 12,不输出 |
12 |
移除 12 |
|
0,输出 |
表中 active 保留的是会影响未来最高高度的状态,而 previous_height 只保留输出压缩所需的上一条水平线。
两者职责不同,不能用已经输出的点替代活动建筑集合。
代码走读¶
事件构造把每座建筑的左右边界各记录一次,排序后外层循环负责坐标推进,内层循环负责该坐标的状态转移, 最后才观察最高高度。这个顺序删除了“每个横坐标重新扫描全部建筑”的工作,也避免把同坐标的零宽度变化写入结果。
复杂度与边界¶
有 n 座建筑时事件数为 2n,排序耗时 O(n log n);每个事件对多重集合进行一次 O(log n) 的插入或删除,
总时间仍为 O(n log n),事件数组和活动集合占 O(n) 额外空间,返回的关键点空间另计。空输入不产生事件,
高度 0 哨兵保证最后一座建筑移除后仍能读取最高高度;left < right 保证每个结束事件对应此前加入的建筑。