218. The Skyline Problem

刷
June-20-2019

这个题还是蛮好的啦~（台湾腔）这个人还是长得蛮像个傻逼的啦。。
最后的答案只需要[startX, height]就行了，而且第一个0的高度是不需要的= =

给的各种[start, end, height]，需要按照start来排序，目的是从左到右建立各种高度的区间。
[3, 10, 4] [5, 10, 12]

[3, 12, 4]比如，从3开始有高度为4的建筑[3, 4]，持续到12 => [12, -4]
第二个是[5, 10, 12]， 从5开始变为12[5, 12]，持续到10, [10, -12]
后面的负数代表到什么地方结束,所以上面的2个区间最后变为下面这种排序的list:
[3,4][5,12][10, -12][12, -4]

问题在于到10之后，我们知道5-10这段结束了，现在怎么回到3的高度。解决的方法是用类似于PQ的结构找到第二高的。

看起来很简单= = 然后各种case的处理比较麻烦，
比如2个建筑一样高[1,2,3][1,2,4],小的应该直接无视。
比如高的楼下面小的，应该被无视，第一个第二个小的要删除。要从PQ里找第二小的删除，那PQ就不行了

再比如一段很高的楼下面，有若干高度相等的小楼，所以不光要记得第二高的，还要记得第二高的有多少个= = 要找到最右边的才行

反正最后他妈的使用TreeMap了，<Height, Count> count = 当前高度有几段.

Time:
建 O(n) n = # of buildings
sort = O(NlgN)
build: put(), get(), remove() ... O(lgN) * N

最后O(NlgN)

class Solution {
    
    public class Interval {
        int start;
        int height;
        public Interval(int start, int height) {
            this.start = start;
            this.height = height;
        }
    }
    
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();
        if (buildings == null || buildings.length == 0) return res;
        
        List<Interval> intervals = new ArrayList<>(buildings.length * 2);
        
        for (int[] building : buildings) {
            intervals.add(new Interval(building[0], building[2]));
            intervals.add(new Interval(building[1], -building[2]));
        }
        
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                if (a.start != b.start) {
                    return Integer.compare(a.start, b.start);
                } else {
                    return Integer.compare(b.height, a.height);
                }
            }
        });
        
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(0, 1);
        int currentHeight = 0;
        
        for (Interval interval : intervals) {
            int start = interval.start;
            int height = interval.height;
            
            if (height > 0) {
                map.put(height, map.getOrDefault(height, 0) + 1);
            } else {
                int remain = map.get(-height) - 1;
                if (remain == 0) {
                    map.remove(-height);
                } else {
                    map.put(-height, remain);
                }
            }
            
            int tempHighest = map.lastKey();
            if (tempHighest == currentHeight) {
                // overriden, do nothing.
            } else {
                res.add(Arrays.asList(start, tempHighest));
                currentHeight = tempHighest;
            }
            
        }
        
        return res;
    }
}

Interval里高度，负数代表结束。
排序也说过了，按start；start一样，高的在前面，这样小的会被无视。
map(height, count)
treeMap.lastKey()找到最大的KEY，要记住key是sorted.
然后生成答案的时候

• 找到start，入map，count++
  
• 找到end，count --，如果等于0就删了。

tempHeight是每次选取MAP里最高的。
currentHeight其实是正在进行的高度。这俩一比较，一样就不动，不一样按新得的tempHeight来，因为最终答案不记录end,所以不一样其实就代表上一个高度的线结束了。

218. The Skyline Problem

原文：https://www.cnblogs.com/reboot329/p/11063577.html