LeetCode[218] The Skyline Problem

keithyau 發(fā)布于2019-08-14 15:57 / 1151人閱讀

摘要：復(fù)雜度思路利用的思想，先分成左右兩部分，再進(jìn)行。每次都要將的左上角和右下角推進(jìn)，進(jìn)行計(jì)算。觀察左邊和右邊進(jìn)行。

LeetCode[218] The Skyline Problem

A city"s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet
of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the
left and right edge of the ith building, respectively, and Hi is its

It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX,

Ri - Li > 0. You may assume all buildings are perfect rectangles


grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded
as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

Divide & Conquer

復(fù)雜度
O(NlgN), O(N)

思路
利用merge sort的思想，先分成左右兩部分，再進(jìn)行merge。每次都要將building的左上角和右下角推進(jìn)priorityQueue，進(jìn)行計(jì)算。觀察左邊和右邊進(jìn)行merge。

代碼

public List getKyLine(int[][] buildings) {
    return merge(buildings, 0, buildings.length - 1);
}

public LinkedList merge(int[][] buildings, int lo, int hi) {
    LinkedList res = new LinkedList<>();
    if(lo > hi) {
        return res;
    }
    else if(lo == hi) {
        res.add(new int[]{buildings[lo][0], buildings[lo][2]};
        res.add(new int[]{buildings[lo][0], 0});
        return res;
    }
    int mid = lo + (hi - lo) / 2;
    LinkedList left = merge(buildings, lo, mid);
    LinkedList right = merge(buildings, mid + 1, hi);
    int leftH = 0, rightH = 0;
    while(!left.isEmpty() || !right.isEmpty()) {
        long x1 = left.isEmpty() ? Long.MAX_VALUE : left.peekFirst()[0];
        long x2 = right.isEmpty() ? Long.MAX_VALUE : right.peekFirst()[0];
        int x = 0;
        if(x1 < x2) {
            int[] temp = left.pollFirst();
            x = temp[0];
            leftH = temp[1];
        }
        else if(x1 > x2) {
            int[] temp = right.pollFirst();
            x = temp[0];
            rightH = temp[1];
        }
        else {
            x = left.peekFirst()[0];
            leftH = left.pollFirst()[1];
            rightH = right.pollFirst()[1];
        }
        int h = Math.max(leftH, rightH);
        if(res.isEmpty() || h != res.peekFirst()[1]) {
            res.add(new int[]{x, h});
        }
        return res;
    }
}