题目描述：

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

 

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

The number of buildings in any input list is guaranteed to be in the range [0, 10000].

The input list is already sorted in ascending order by the left x position Li.

The output list must be sorted by the x position.

There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

题目大意：

一座城市的天际线是指从远处观察城市，所有建筑侧影的外部轮廓。现在假设给定所有建筑的位置和高度，如城市景观照片（图A）所示，编写程序输出这些建筑形成的天际线（图B）。

每一座建筑的地理信息由一个整数三元组 [Li, Ri, Hi] 指定， 其中Li 与 Ri分别是第i座城市的左右边缘，Hi为其高度。题目保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, 并且 Ri - Li > 0。你可以假设所有的建筑都是完美的矩形，位于一个绝对平坦且高度为0的平面之上。

例如，图A中所有建筑的坐标是：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。

输出是一列可以唯一标识天际线的“关键点”（图B中的红点），形如 [ [x1,y1], [x2, y2], [x3, y3], ... ] 。关键点是指水平线段的左端点。注意最后一个关键点，即城市边缘的最右端，仅仅是用来标识天际线的终点，其高度永远为0。并且，任意两个相邻建筑之间的平地也应视为天际线的一部分。

例如，图B的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。

注意：

任意输入的建筑物总数在范围[0, 10000]之内

输入的列表是按照位置Li的左端点递增有序的。

输出列表必须按照x坐标排序。

在天际线中不可以存在连续的等高水平线段。例如，[...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的；其中的三条线段高度均为5，因此应该合并输出为： [...[2 3], [4 5], [12 7], ...]

解题思路：

从左向右扫描线段的起点与终点，使用最大堆(Max Heap)维护线段的最大值

当端点为起点时，向最大堆内插入一个线段

当端点为终点时，从最大堆中移除相应线段

在扫描的过程中，注意端点重合与高度相同时对结果列表的维护

Python代码：

class MaxHeap:
    def __init__(self, buildings):
        self.buildings = buildings
        self.size = 0
        self.heap = [None] * (2 * len(buildings) + 1)
        self.lineMap = dict()
    def maxLine(self):
        return self.heap[1]
    def insert(self, lineId):
        self.size += 1
        self.heap[self.size] = lineId
        self.lineMap[lineId] = self.size
        self.siftUp(self.size)
    def delete(self, lineId):
        heapIdx = self.lineMap[lineId]
        self.heap[heapIdx] = self.heap[self.size]
        self.lineMap[self.heap[self.size]] = heapIdx
        self.heap[self.size] = None
        del self.lineMap[lineId]
        self.size -= 1
        self.siftDown(heapIdx)
    def siftUp(self, idx):
        while idx > 1 and self.cmp(idx / 2, idx) < 0:
            self.swap(idx / 2, idx)
            idx /= 2
    def siftDown(self, idx):
        while idx * 2 <= self.size:
            nidx = idx * 2
            if idx * 2 + 1 <= self.size and self.cmp(idx * 2 + 1, idx * 2) > 0:
                nidx = idx * 2 + 1
            if self.cmp(nidx, idx) > 0:
                self.swap(nidx, idx)
                idx = nidx
            else:
                break
    def swap(self, a, b):
        la, lb = self.heap[a], self.heap[b]
        self.lineMap[la], self.lineMap[lb] = self.lineMap[lb], self.lineMap[la]
        self.heap[a], self.heap[b] = lb, la
    def cmp(self, a, b):
        return self.buildings[self.heap[a]][2] - self.buildings[self.heap[b]][2]

class Solution:
    def getSkyline(self, buildings):
        size = len(buildings)
        points = sorted([(buildings[x][0], x, 's') for x in range(size)] + 
                        [(buildings[x][1], x, 'e') for x in range(size)])
        maxHeap = MaxHeap(buildings)
        ans = []
        for p in points:
            if p[2] == 's':
                maxHeap.insert(p[1])
            else:
                maxHeap.delete(p[1])
            maxLine = maxHeap.maxLine()
            height = buildings[maxLine][2] if maxLine is not None else 0
            if len(ans) == 0 or ans[-1][0] != p[0]:
                ans.append([p[0], height])
            elif p[2] == 's':
                ans[-1][1] = max(ans[-1][1], height)
            else:
                ans[-1][1] = min(ans[-1][1], height)
            if len(ans) > 1 and ans[-1][1] == ans[-2][1]:
                ans.pop()
        return ans

 

本文链接：http://bookshadow.com/weblog/2015/08/14/leetcode-the-skyline-problem/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码