LeetCode218. 天际线问题

题目链接：LeetCode218

题解

如果按照一个矩形一个矩形处理会非常麻烦，我们把这些矩形拆成两个点，一个左上角顶点，一个右上角顶点。将所有顶点按照横坐标进行排序然后开始遍历，遍历时通过一个堆来得知当前图形的最高位置，堆顶是所有顶点中最高的点，只要这个点没被移出堆，就说明这个最高的矩形还没结束。对于左顶点，我们将其加入堆中，对于右顶点，我们找出堆中相应的最顶点，然后移出左顶点，同时也意味着这个矩形的结束，为了区分左右顶点，我们以负数作为左顶点，正数作为右顶点

代码

public class Solution {
        public static List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new ArrayList<>();
        List<int[]> height = new ArrayList<>();
        // 拆解矩形的左右顶点
        for (int[] b : buildings) {
            height.add(new int[] { b[0], -b[2] });// 左顶点存负数
            height.add(new int[] { b[1], b[2] });// 右顶点存正数
        }
        // 根据横坐标对列表排序，相同横坐标的点纵坐标小的排在前面
        Collections.sort(height, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0])
                    return a[0] - b[0];
                return a[1] - b[1];
            }
        });
        // 构建堆
        Queue<Integer> pq = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        pq.add(0);// 首先加入地平线起始点0
        int prev = 0;// prev用于记录上次keyPoint的高度
        for (int[] h : height) {
            if (h[1] < 0)// 左顶点加入堆
                pq.add(-h[1]);
            else
                pq.remove(h[1]);// 将右顶点对应的左顶点移出
            int cur = pq.peek();
            if (prev != cur) {// 如果堆的新顶部和上个keypoint高度不一样，则加入一个新的keypoint
                res.add(new int[] { h[0], cur });
                prev = cur;
            }
        }
        return res;
    }
}