218 The Skyline Problem

TreeMap可以动态地获取最值，可以实时知道添加或者去掉某个值之后的最值是多少，但是它是全局的，也就是说不像max stack一样能知道当前值之前和之后的第一个高值。当然如果treemap是有方向性的更新，比如指针从左往右依次更新，treemap也可以只反映已经探索到的区域的最值。

key idea是把它们都看作点，遇到start就记录高度，遇到end就剔除高度，然后看遇到每个可能的转折点时的最大高度值，这里关键在于剔除高度之后怎么知道当前位置最大值变成了多少，这里是使用了treemap来更新。之所以知道treemap里的最大值就是当前位置的最大值是因为如果这个最大值没有延续到当前位置那早就在之前的更新中被剔除掉了。

skyline其实就是每个区间里最高的值，换个角度想每一个当前最高的值只会在对应的区间出现，而这个值只会在转折处发生改变。

似乎也可以用线段树做

class Solution {
    class Point {
        public int x;
        public boolean start;
        public int height;
        public Point(int x, boolean s, int h) {
            this.x = x;
            this.start = s;
            this.height = h;
        }
    }
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();
        // x coord -> point
        TreeMap<Integer, List<Point>> map = new TreeMap<>();
        // 把building的起止端各自当作节点存进map里
        for (int i = 0; i < buildings.length; i++) {
            List<Point> list = map.get(buildings[i][0]);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(new Point(buildings[i][0], true, buildings[i][2]));
            map.put(buildings[i][0], list);
            
            list = map.get(buildings[i][1]);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(new Point(buildings[i][1], false, buildings[i][2]));
            map.put(buildings[i][1], list);
        }
        // height -> number of points that has this height
        TreeMap<Integer, Integer> heights = new TreeMap<>(Collections.reverseOrder());
        // 按横坐标从左往右遍历所有point，更新高度记录，which只会在segment start和end的时候变化
        for (Map.Entry<Integer, List<Point>> entry : map.entrySet()) {
            for (Point p : entry.getValue()) {
                int height = p.height;
                // starting point就把height加入高度记录中
                if (p.start) {
                    int cnt = heights.getOrDefault(p.height, 0);
                    heights.put(p.height, cnt + 1);
                } else {
                // ending point就把height从高度记录中扣除  
                    int cnt = heights.get(p.height);
                    if (cnt == 1) {
                        heights.remove(p.height);
                    } else {
                        heights.put(p.height, cnt - 1);
                    }
                }
            }
            // 更新之后记录当前点的最大height
            int h = heights.isEmpty()? 0 : heights.firstKey();
            // 合并一下高度一样的的
            if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) {
                res.add(Arrays.asList(new Integer[]{entry.getKey(), h}));
            }
        }
        return res;
    }
}

当然你也可以不用treemap汇总，而是直接把points汇总成一个list然后sort，但是同样的同一个coordination只应该添加一次，所以只在每个coordination上有的height都探索完之后更新

class Solution {
    class Entry {
        int coord;
        int height;
        boolean start;
        public Entry(int c, int h, boolean s) {
            this.coord = c;
            this.height = h;
            this.start = s;
        }
    }
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<Entry> points = new ArrayList<>();
        for (int[] b : buildings) {
            points.add(new Entry(b[0], b[2], true));
            points.add(new Entry(b[1], b[2], false));
        }
        Collections.sort(points, (Entry e1, Entry e2) -> {
            return e1.coord - e2.coord;
        });
        List<List<Integer>> ans = new ArrayList<>();
        // height -> number of points that has the height
        TreeMap<Integer, Integer> heights = new TreeMap<>(Collections.reverseOrder());
        for (int i = 0; i < points.size(); i++) {
            Entry e = points.get(i);
            if (e.start) {
                heights.put(e.height, heights.getOrDefault(e.height, 0) + 1);
            } else {
                int cnt = heights.get(e.height);
                if (cnt == 1) {
                    heights.remove(e.height);
                } else {
                    heights.put(e.height, cnt - 1);
                }
            }
            // heights可能为空
            int height = heights.isEmpty() ? 0 : heights.firstKey();
            // 只在相同的值结束时更新，防止同一个点出现多个值
            if ((i == points.size() - 1 || e.coord != points.get(i+1).coord) 
            && (ans.size() == 0 || ans.get(ans.size() -1 ).get(1) != height)) {
                ans.add(Arrays.asList(new Integer[]{e.coord, height}));
            }
        }
        return ans;
    }
}