218._The_Skyline_Problem.md

218. The Skyline Problem

题目: https://leetcode.com/problems/The-Skyline-Problem/

难度:

Hard

思路

观察发现，skyline的points的横坐标一定是某个building的左边界或者右边界。

开始，假设只有2个建筑物，拿出第一个buiding B1，我们先把它的左上顶点加进我们的output结果skyline中，然后继续拿下一个building B2，我们现在需要将B2的左上顶点对应的x coordinate与B1的右上顶点所对应的x coordinate做比较：

• 如果前者小且B2的高度大于B1的高度，则我们将B2的左上顶点也加入skyline中去。
• 如果前者小且B2的高度小于等于B1的高度，则忽略B2的左上顶点

接下来考虑更多建筑物的情况，从左到右扫描，当我们遇到第一个楼的左边界时，把它push到一个heap中。如果后面扫描的楼的高度比heap中最高的楼还高，那么它的左上顶点一定会被加入到skyline中。当我们遇到一个building的右边界时,我们需要将其从heap中pop掉，如果heap中max height有变化，则push到结果中。

参考Brian Gordon的blog 和 Stefan大神的题解

程序代码解释

• liveBuildings代表（左上顶点已经被加入output中但右上顶点还没有做判断的building）的右上顶点的集合，形式为[(height, x-coordinate)…..]
• skyline是output
• 程序里面的这句代码while idx < n and buildings[idx][0] == start:是为了防止有左右坐标完全相同但是height不同的building的存在，it's not useless!!!
• python里面的heapq模块如果有不懂的同学可以看看这个文章：heapq

class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        idx, n = 0, len(buildings)
        liveBuildings, skyline = [], []
        while idx < n or len(liveBuildings) > 0: # 只要所有的点没处理完就一直循环
            if len(liveBuildings) == 0 or (idx < n and buildings[idx][0] <= -liveBuildings[0][1]):
                start = buildings[idx][0]
                while idx < n and buildings[idx][0] == start:
                    heapq.heappush(liveBuildings, [-buildings[idx][2], -buildings[idx][1]])
                    idx += 1
            else:
                start = -liveBuildings[0][1]
                while len(liveBuildings) > 0 and -liveBuildings[0][1] <= start:
                    heapq.heappop(liveBuildings)
            height = len(liveBuildings) and -liveBuildings[0][0]
            if len(skyline) == 0 or skyline[-1][1] != height:
                skyline.append([start, height])
        return skyline

#####另外还有一个超级6的大神的代码，但是今天我要赶报告，就只先贴代码了

class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        events = sorted([(L, -H, R) for L, R, H in buildings] + list(set((R, 0, None) for L, R, H in buildings)))
        #events = sorted(event for L, R, H in buildings for event in ((L, -H, R), (R, 0, None)))
        res, hp = [[0, 0]], [(0, float("inf"))]
        for x, negH, R in events:
            while x >= hp[0][1]: 
                heapq.heappop(hp)
            if negH: heapq.heappush(hp, (negH, R))
            if res[-1][1] + hp[0][0]: 
                res += [x, -hp[0][0]],
        return res[1:]

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return result;
        }
        
        List<Height> heights = new ArrayList<Height>();
        for (int[] building : buildings) {
            heights.add(new Height(building[0], -building[2]));
            heights.add(new Height(building[1], building[2]));
        }
        Collections.sort(heights, new Comparator<Height>() {
            @Override
            public int compare(Height h1, Height h2) {
                return h1.index != h2.index ? h1.index - h2.index : h1.height - h2.height;
            }
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(1000, Collections.reverseOrder());
        pq.offer(0);
        int prev = 0;
        for (Height h : heights) {
            if (h.height < 0) {
                pq.offer(-h.height);
            } else {
                pq.remove(h.height);
            }
            int cur = pq.peek();
            if (cur != prev) {
                result.add(new int[]{h.index, cur});
                prev = cur;
            }
        }
        
        return result;
    }
    
    class Height {
        int index;
        int height;
        Height(int index, int height) {
            this.index = index;
            this.height = height;
        }
    }
}

Author: Keqi Huang

If you like it, please spread your support