MENU

LeetCode218. 天际线问题

August 14, 2018 • Read: 438 • LeetCode

题目链接: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;
    }
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment