[LeetCode]218. 天际线问题(The Skyline Problem)

题目描述

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在,假设您获得了城市风光照片(图A)上显示的所有建筑物的位置和高度,请编写一个程序以输出由这些建筑物形成的天际线(图B)。

每个建筑物的几何信息用三元组 [Li,Ri,Hi] 表示,其中 LiRi 分别是第 i 座建筑物左右边缘的 x 坐标,Hi 是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAXRi - Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。

例如,图A中所有建筑物的尺寸记录为:[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]

输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的“关键点”(图B中的红点)的列表,它们唯一地定义了天际线。关键点是水平线段的左端点。请注意,最右侧建筑物的最后一个关键点仅用于标记天际线的终点,并始终为零高度。此外,任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

例如,图B中的天际线应该表示为:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]

说明:

  • 任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。
  • 输入列表已经按左 x 坐标 Li 进行升序排列。
  • 输出列表必须按 x 位排序。
  • 输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案;三条高度为 5 的线应该在最终输出中合并为一个:[...[2 3], [4 5], [12 7], ...]

解题思路

采用最大堆。

  1. 将建筑物的左右边界存下来;
  2. 遍历所有边界,若其为某个建筑物的左边界,则将建筑物右边界和高度入堆;
  3. 若最大堆堆顶元素的右边界小于等于(因为若某个最大值是右边界,则最后存的不是该高度,而是除他之外最大的值,如例子中的 7)当前边界值,将其出堆;
  4. 取堆顶元素的建筑物高,若其不等于前一次的关键点,则说明该点与上一次的点不在一条水平线上,为一个“关键点”。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
import heapq
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
borders = sorted([i[0] for i in buildings] + [i[1] for i in buildings])
index = 0
heap = []
res = [[0, 0]]
for border in borders:
while index < len(buildings) and buildings[index][0] == border:
heapq.heappush(heap, [-buildings[index][2], buildings[index][1]])
index += 1
while heap and heap[0][1] <= border:
heapq.heappop(heap)
heigh = -heap[0][0] if heap else 0
if heigh != res[-1][1]:
res.append([border, heigh])
return res[1:]

执行用时: 92 ms
内存消耗: 16.9 MB

参考

https://leetcode-cn.com/problems/the-skyline-problem/comments/101001