218. The Skyline Problem
难度: Hard
刷题内容
原题连接
- https://leetcode.com/problems/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).
Buildings Skyline Contour
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 height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and 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] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
The number of buildings in any input list is guaranteed to be in the range [0, 10000].
The input list is already sorted in ascending order by the left x position Li.
The output list must be sorted by the x position.
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
解题方案
思路 1 **- 时间复杂度: O(N^2)*- 空间复杂度: O(N)***
观察发现，skyline的points的横坐标一定是某个building的左边界或者右边界。
开始，假设只有2个建筑物，拿出第一个buiding B1，我们先把它的左上顶点加进我们的output结果skyline中，然后继续拿下一个building B2，我们现在需要将B2的左上顶点对应的x coordinate与B1的右上顶点所对应的x coordinate做比较：
- 如果前者小且B2的高度大于B1的高度，则我们将B2的左上顶点也加入skyline中去。
- 如果前者小且B2的高度小于等于B1的高度，则忽略B2的左上顶点
接下来考虑更多建筑物的情况，从左到右扫描，当我们遇到第一个楼的左边界时，把它push到一个heap中。如果后面扫描的楼的高度比heap中最高的楼还高，那么它的左上顶点一定会被加入到skyline中。当我们遇到一个building的右边界时,我们需要将其从heap中pop掉，如果heap中max height有变化，则push到结果中。
参考Brian Gordon的blog 和 Stefan大神的题解
public class Solution {
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<int[]>();
if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
return result;
}
List<Height> heights = new ArrayList<Height>();
for (int[] building : buildings) {
heights.add(new Height(building[0], -building[2]));
heights.add(new Height(building[1], building[2]));
}
Collections.sort(heights, new Comparator<Height>() {
@Override
public int compare(Height h1, Height h2) {
return h1.index != h2.index ? h1.index - h2.index : h1.height - h2.height;
}
});
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(1000, Collections.reverseOrder());
pq.offer(0);
int prev = 0;
for (Height h : heights) {
if (h.height < 0) {
pq.offer(-h.height);
} else {
pq.remove(h.height);
}
int cur = pq.peek();
if (cur != prev) {
result.add(new int[]{h.index, cur});
prev = cur;
}
}
return result;
}
class Height {
int index;
int height;
Height(int index, int height) {
this.index = index;
this.height = height;
}
}
}
