Heap (PriorityQueue)

经典题目

218 The Skyline Problem

几何题，考虑用扫描线方法（与Y轴平行）解决。

首先看几个特征。每个building有2个点，左边界和右边界。当扫描线扫到左边界时，如果当前左边界为最高（对谁而言？）的点，那么该点必然为skyline之一；当扫描线扫到右边界时，如果该点为第二高（对谁而言？）的点，那么该点也为skyline之一。

这里最高，第二高是指当前有效的building高度，即同一区块。也就是说，当扫描线扫到别的区块时，之前的区块的点都不应该考虑。这里我们想到用maxHeap的方式，左边界时入堆，右边界时出堆。

同时，有几种特殊情况需要考虑。第一种，两building左右相接，此时，相接处的点应首先考虑最高点（如考虑最低点，则会多出一个错误的点）。第二种，两building重合，左边界应首先考虑最高点，右边界应首先考虑最低点。所以这也是为什么我们把右边界的高度改为-h的原因。

class Point {
    int x;
    int h;
    public Point(int x, int h) {
        this.x = x;
        this.h = h;
    }
}

class MyComparator implements Comparator<Point> {
    @Override
    public int compare(Point p1, Point p2) {
        if (p1.x == p2.x) {
            return p2.h - p1.h;
        }
        return p1.x - p2.x;
    }
}

public List<int[]> getSkyline(int[][] buildings) {
    List<int[]> res = new ArrayList<>();
    List<Point> list = getSortedList(buildings);
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    maxHeap.offer(0);
    for (Point p : list) {
        int h = p.h;
        int x = p.x;
        if (h > 0) {
            if (h > maxHeap.peek()) {
                res.add(new int[] {x, h});
            }
            maxHeap.offer(h);
        } else {
            h = -h;
            maxHeap.remove(h);
            if (h > maxHeap.peek()) {
                res.add(new int[] {x, maxHeap.peek()});
            }
        }
    }
    return res;
}

private List<Point> getSortedList(int[][] buildings) {
    List<Point> list = new ArrayList<>();
    for (int[] b : buildings) {
        Point leftBoundary = new Point(b[0], b[2]);
        Point rightBoundary = new Point(b[1], -b[2]);
        list.add(leftBoundary);
        list.add(rightBoundary);
    }
    Collections.sort(list, new MyComparator());
    return list;
}