建筑物天际线

Question

我在努力理解天际线的问题。给定n矩形建筑，我们需要计算天际线。我很难理解这个问题的输出。

投入：(1,11,5)，(2,6,7)，(3,13,9)，(12,7,16)，(14,3,25)，(19,18,22)，(23,13,29)，(24,4,28) } 输出天际线：(1，11)，(3，13)，(9，0)，(12，7)，(16，3)，(19，18)，(22，3)，(25，0)

输出是对(xaxis, height)。为什么第三对(9,0)？如果我们看到天际线图，x轴值9的高度是13，而不是0.为什么要显示0？换句话说，如果我们使用第一个建筑(输入(1,11,5))，输出就是(1, 11)，(5, 0)。你们能解释一下为什么是(5,0)而不是(5,11)吗？

Answer 1

把屋顶的间隔想象为左边是封闭的，右边是开放的。

Answer 2

您的输出并不表示“在x-高度为y"，而是”在x-高度变化为y“。

Answer 3

使用扫描行算法；下面是我的python版本解决方案：

class Solution:
    # @param {integer[][]} buildings
    # @return {integer[][]}
    def getSkyline(self, buildings):
        if len(buildings)==0: return []
        if len(buildings)==1: return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

        points=[]
        for building in buildings:
            points+=[[building[0],building[2]]]
            points+=[[building[1],-building[2]]]
        points=sorted(points, key=lambda x: x[0])

        moving, active, res, current=0, [0], [],-1

        while moving<len(points):
            i=moving
            while i<=len(points):
                if i<len(points) and points[i][0]==points[moving][0]:
                    if points[i][1]>0:
                        active+=[points[i][1]]
                        if points[i][1]>current:
                            current=points[i][1]
                            if len(res)>0 and res[-1][0]==points[i][0]: 
                                res[-1][1]=current
                            else:
                                res+=[[points[moving][0], current]]
                    else:
                        active.remove(-points[i][1])
                    i+=1
                else:
                    break

            if max(active)<current:
                current=max(active)
                res+=[[points[moving][0], current]] 
            moving=i
        return res