天际线

力扣218

Posted by songjiu on May 22, 2019

onsite如果遇到这个题我直接GG回家谢谢惠顾。

题目概述

题目概述

题目分析

有点难度,折腾了一天才看懂别人的代码。总而言之,满足最终结果的点,如果看作高度与横坐标的二元组,其中高度满足:与前一次不同 横坐标满足:不被当前最高峰阻挡,满足这二点的二元组可以加入最终结果。

代码

def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        import heapq
        #buildings=[[2,9,10],[3,7,15],[5,12,13]]
        events = [(L,-H,R) for L,R,H in buildings]
        events += list((R,0,0) for _,R,_ in buildings)
        events.sort()
        print(events)
        #将全部的线段以 左端点坐标、高度的负数、右端点坐标的格式加入events,并将全部右端点以: 右端点坐标、高度(0)、(0)加入events,这样events当中的全部三元组的第一位(for i in events 的 i[0])就包含了最终全部有可能的结果的横坐标,而三元组的第二位(for i in events 的 i[1])就对应包含了全部有可能的结果的高度。
        #然后在将这些三元组(包括线段三元组与右端点三元组)按照升序排列,也就是从左到右开始判断全部可能出现符合要求的点的位置
        res = [[0,0]]
        live = [(0,float('inf'))]
        for L,negH,R in events:
            #print(live)
            if negH<0:#这里是为了判断events是存储的线段还是右端点,如果是存储的是线段,则需要将他的右端点与最高高度存入live(也就是live包含了全部 线段三元组的高度高度与右边界)
                heapq.heappush(live,(negH,R))
            #print(live)
            while live[0][1] <= L:#由于使用了“heapq ”堆排序二叉树模块,所以live[0]永远是live这个list的里面最小的,由于存储的是负数,所以也就代表当前最高的。当当前三元组的左端都比最高峰的右端还大的时候,说明此时最高峰已经与当前三元组无交集无重合,因此pop
                heapq.heappop(live)#
            #print(live)
            if res[-1][1] != -live[0][0]:#只要当前最高峰与最新加入res的高度有所不同,那么就将他加入res
                res += [[L,-live[0][0]]]
            #总而言之,加入res当中的点分为高度h和横坐标来看,其中高度满足:与前一次不同 横坐标满足:不被最高峰阻挡,满足这二点的二元组可以加入 res。
            #print(L,negH,R)
            #print(res)
            #print(live)
        #print(res)
        return res[1:]