0218. The Skyline Problem

题目信息

题号:
  1. 天际线问题

难度:

Hard

主题:

扫描线、事件排序、多重集合、轮廓压缩

原题:

LeetCode 0218

重点:

半开区间、活动建筑、同坐标批处理、最高高度变化

题目重述

每座建筑用 [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]],处理完每个坐标组后的状态如下:

坐标

事件变化

active

新高度与输出

2

加入 10

{0,10}

10,输出 [2,10]

3

加入 15

{0,10,15}

15,输出 [3,15]

5

加入 12

{0,10,12,15}

仍为 15,不输出

7

移除 15

{0,10,12}

12,输出 [7,12]

9

移除 10

{0,12}

仍为 12,不输出

12

移除 12

{0}

0,输出 [12,0]

表中 active 保留的是会影响未来最高高度的状态,而 previous_height 只保留输出压缩所需的上一条水平线。 两者职责不同,不能用已经输出的点替代活动建筑集合。

代码走读

事件构造把每座建筑的左右边界各记录一次,排序后外层循环负责坐标推进,内层循环负责该坐标的状态转移, 最后才观察最高高度。这个顺序删除了“每个横坐标重新扫描全部建筑”的工作,也避免把同坐标的零宽度变化写入结果。

复杂度与边界

有 n 座建筑时事件数为 2n,排序耗时 O(n log n);每个事件对多重集合进行一次 O(log n) 的插入或删除, 总时间仍为 O(n log n),事件数组和活动集合占 O(n) 额外空间,返回的关键点空间另计。空输入不产生事件, 高度 0 哨兵保证最后一座建筑移除后仍能读取最高高度;left < right 保证每个结束事件对应此前加入的建筑。