难度: Hard
原题连接
内容描述
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
Buildings Skyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
The number of buildings in any input list is guaranteed to be in the range [0, 10000].
The input list is already sorted in ascending order by the left x position Li.
The output list must be sorted by the x position.
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
观察发现，skyline的points的横坐标一定是某个building的左边界或者右边界。
开始，假设只有2个建筑物，拿出第一个buiding B1，我们先把它的左上顶点加进我们的output结果skyline中，然后继续拿下一个building B2，我们现在需要将B2的左上顶点对应的x coordinate与B1的右上顶点所对应的x coordinate做比较：
- 如果前者小且B2的高度大于B1的高度，则我们将B2的左上顶点也加入skyline中去。
- 如果前者小且B2的高度小于等于B1的高度，则忽略B2的左上顶点
接下来考虑更多建筑物的情况，从左到右扫描，当我们遇到第一个楼的左边界时，把它push到一个heap中。如果后面扫描的楼的高度比heap中最高的楼还高，那么它的左上顶点一定会被加入到skyline中。当我们遇到一个building的右边界时,我们需要将其从heap中pop掉，如果heap中max height有变化，则push到结果中。
参考Brian Gordon的blog 和 Stefan大神的题解
- liveBuildings代表（左上顶点已经被加入output中但右上顶点还没有做判断的building）的右上顶点的集合，形式为[(height, x-coordinate)…..]
- skyline是output
- 程序里面的这句代码
while idx < n and buildings[idx][0] == start:是为了防止有左右坐标完全相同但是height不同的building的存在，it's not useless!!! - python里面的heapq模块如果有不懂的同学可以看看这个文章：heapq
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
idx, n = 0, len(buildings)
liveBuildings, skyline = [], []
while idx < n or len(liveBuildings) > 0: # 只要所有的点没处理完就一直循环
# 如果没有liveBuildings或者当前building的左边界小于等于前面高度最高且右边界最大的liveBuilding的右边界
if len(liveBuildings) == 0 or (idx < n and buildings[idx][0] <= -liveBuildings[0][1]):
start = buildings[idx][0] # 当前building的左边界
while idx < n and buildings[idx][0] == start: # 只要当前building的左边界不变，就一直往堆里放
heapq.heappush(liveBuildings, [-buildings[idx][2], -buildings[idx][1]])
idx += 1
else: # 如果有liveBuildings且当前building的左边界大于前面高度最高且右边界最大的liveBuilding的右边界
start = -liveBuildings[0][1] # 前面高度最高且右边界最大的liveBuilding的右边界
# 只要还有liveBuilding，pop掉所有右边界较小(高度必然比start对应liveBuilding小)的liveBuilding
while len(liveBuildings) > 0 and -liveBuildings[0][1] <= start:
heapq.heappop(liveBuildings)
height = len(liveBuildings) and -liveBuildings[0][0]
if len(skyline) == 0 or skyline[-1][1] != height:
skyline.append([start, height])
return skyline思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
另外还有一个超级6的大神的代码，但是今天我要赶报告，就只先贴代码了
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
events = sorted([(L, -H, R) for L, R, H in buildings] + list(set((R, 0, None) for L, R, H in buildings)))
#events = sorted(event for L, R, H in buildings for event in ((L, -H, R), (R, 0, None)))
res, hp = [[0, 0]], [(0, float("inf"))]
for x, negH, R in events:
while x >= hp[0][1]:
heapq.heappop(hp)
if negH: heapq.heappush(hp, (negH, R))
if res[-1][1] + hp[0][0]:
res += [x, -hp[0][0]],
return res[1:]