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 只是累累病==