0218. The Skyline Problem ========================= 题目信息 -------- :题号: 0218. 天际线问题 :难度: Hard :主题: 扫描线、事件排序、多重集合、轮廓压缩 :原题: `LeetCode 0218 `_ :重点: 半开区间、活动建筑、同坐标批处理、最高高度变化 题目重述 -------- 每座建筑用 ``[left, right, height]`` 表示,覆盖半开区间 ``left <= x < right``,高度为正整数;建筑之间可以重叠、包含, 也可以只在边界接触。返回从左到右的外轮廓关键点 ``[x, height]``:在横坐标 ``x`` 右侧,轮廓高度发生变化时输出该点, 最后必须回到高度 0;连续保持同一高度的区间不能拆成多个点。建筑数量最多为 ``10^4``,每座建筑保证 ``left < right``。 自建示例 -------- 两座建筑部分重叠: .. code-block:: text 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++ 实现 -------- .. code-block:: cpp #include #include #include #include class Solution { public: std::vector> getSkyline( std::vector>& buildings) { std::vector> events; events.reserve(buildings.size() * 2); for (const std::vector& building : buildings) { events.push_back({building[0], -building[2]}); events.push_back({building[1], building[2]}); } std::sort(events.begin(), events.end()); std::multiset active{0}; std::vector> 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]]``,处理完每个坐标组后的状态如下: .. list-table:: :header-rows: 1 * - 坐标 - 事件变化 - ``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`` 保证每个结束事件对应此前加入的建筑。