摘要：复杂度思路利用的思想，先分成左右两部分，再进行。每次都要将的左上角和右下角推进，进行计算。观察左边和右边进行。
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
复杂度
O(NlgN), O(N)
思路
利用merge sort的思想，先分成左右两部分，再进行merge。每次都要将building的左上角和右下角推进priorityQueue，进行计算。观察左边和右边进行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;
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/66137.html
