天际线问题

天际线问题

构造一个优先队列 把左边缘和对应高度，右边缘和对应高度存储到一个数组中 用左边缘高度为负来区分，依次遍历数组，若为左边缘入队列，若为右边缘出队列，每次入队列和出队列都进行判断，若入队列高度为最高则加入答案，若出队列高度发生改变（把出队列后最高）也加入答案即可。

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        all = []
        for l, r, h in buildings:
            all.append([l,-h])
            all.append([r,h])
        all.sort()

        ans = []
        pq = [0]
        for x, h in all:
            if h < 0:
                tmp = pq[0]
                heappush(pq, h)
                if tmp != pq[0]:
                    ans.append([x, -h])
            else:
                tmp = pq[0]
                pq.remove(-h)
                heapify(pq)
                if tmp != pq[0]:
                    ans.append([x, -pq[0]])
        return ans