218. The Skyline Problem
给你一堆建筑物 要你算出他们的天际线长怎样
思路:
1.sweep line经典题 就跟那个给你出入时间问你派对上有几个人的题很像
状态变化只会只有事件发生点 也就是每个建筑物的加入和结束
只是和派对不同 你要维护的是一群建筑物当中的最高点 没错 就是用heap
2.算出每个事件点 排序 从左扫到右 0代表加入这个建筑物 1代表删除这个建筑物
x座标变化时 看现在的最大高度有没有变 有就加进output
为了比较好删选择用 sorted list
有个做法是只看加入的点 把这建筑物结束的点一起存进heap里
然后在抓heap top的时候看现在的x有没有超过他结束的点 有的话就把他pop掉
可以只用heap完成 写法更漂亮
Python code:
from sortedcontainers import SortedList
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
events = []
for building in buildings:
events.append((building[0], building[2], 0))
events.append((building[1], building[2], 1))
events.sort(key = lambda x: x[0])
events.append((-1, 0, 0))
height = SortedList([0])
currx, currh = 0, 0
res = []
for event in events:
if currx != event[0]:
if currh != height[-1]:
res.append([currx, height[-1]])
currh = height[-1]
currx = event[0]
if event[2] == 0:
height.add(event[1])
elif event[2] == 1:
height.remove(event[1])
return res
不是不PO 只是累累病==