力扣 218 天际线

题意：给定一个大楼的坐标和高度，返回天际线坐标

思路：用队列遍历楼的左右边界，具体见注释

思想：队列

复杂度：时间O（n^{2)，空间O(n}2)

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        if(buildings.length == 0)
            return new ArrayList<List<Integer>>();
        List<int[]> list = new ArrayList();
        // 把building的左右边和高度加入list中，其中右边的高度可以设为负，用来区分左右
        for(int[] b: buildings) {
            int[] left = {b[0], b[2]};
            int[] right = {b[1], 0 - b[2]};
            list.add(left);
            list.add(right);
        }
        // 把点排序，左边的点靠前，如果左边的点相等，那么高度小的靠前
        Collections.sort(list, new Comparator<int[]>(){
            public int compare(int[] n1, int[] n2) {
                if(n1[0] == n2[0])
                    return n2[1] - n1[1];
                return n1[0] - n2[0];
            }
        });
        // 按照高度从大到小排序
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer n1, Integer n2) {
                return n2.compareTo(n1);
            }
        });
        // 把没有点的情况加进去
        pq.add(0);
        int pre = 0;
        List<List<Integer>> res = new ArrayList();
        // 遍历排好序的点，当时左边界的时候，高度加入队列，当是右边界的时候从队列中删除对应的高度，每次加入和删除时，如果队列的高度变更了，那么该坐标加入结果
        for(int[] b: list) {
            if(b[1] < 0) {
                pq.remove(0-b[1]);
                int cur = pq.peek();
                if(pre != cur) {
                    List<Integer> temp = new ArrayList();
                    temp.add(b[0]);
                    temp.add(cur);
                    res.add(temp);
                    pre = cur;
                }
            } else {
                if(pre < b[1]) {
                    List<Integer> temp = new ArrayList();
                    temp.add(b[0]);
                    temp.add(b[1]);
                    res.add(temp);
                    pre = b[1];
                }
                pq.add(b[1]);
            }
        }
        return res;
    }
}