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 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], ...]
Credits:
Special thanks to @stellari for adding this problem, creating these two awesome images and all test cases.
提示：提交代码后，需要用简洁的语言解释一下代码思路~ 谢谢
历史题目和总结见公众号「每日一道算法题」
https://leetcode.com/problems/The-Skyline-Problem/
难度:
Hard
观察发现，
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
到结果中。
-
- liveBuildings
代表（左上顶点已经被加入
output
中但右上顶点还没有做判断的
building
）的右上顶点的集合，形式为
[(height, x-coordinate)…..]
-
- skyline
是
output
-
-
程序里面的这句代码
```while idx < n and buildings[idx][0] == start:```
是为了防止有左右坐标完全相同但是
height
不同的
building
的存在，
it's not useless!!!
-
- python
里面的
heapq
模块如果有不懂的同学可以看看这个文章：
[heapq](http://blog.csdn.net/calling_wisdom/article/details/41676133)
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
idx, n = 0, len(buildings)
liveBuildings, skyline = [], []
while idx < n or len(liveBuildings) > 0:
if len(liveBuildings) == 0 or (idx < n and buildings[idx][0] <= -liveBuildings[0][1]):
start = buildings[idx][0]
while idx < n and buildings[idx][0] == start:
heapq.heappush(liveBuildings, [-buildings[idx][2], -buildings[idx][1]])
idx += 1
else:
start = -liveBuildings[0][1]
while len(liveBuildings) > 0 and -liveBuildings[0][1] <= start:
heapq.heappop(liveBuildings)
height = len(liveBuildings) and -liveBuildings[0][0]
if len(skyline) == 0 or skyline[-1][1] != height:
skyline.append([start, height])
return skyline
另外还有一个超级
6
的大神的代码，但是今天我要赶报告，就只先贴代码了
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
events = sorted([(L, -H, R) for L, R, H in buildings] + list(set((R, 0, None) for L, R, H in buildings)))
#events = sorted(event for L, R, H in buildings for event in ((L, -H, R), (R, 0, None)))
res, hp = [[0, 0]], [(0, float("inf"))]
for x, negH, R in events:
while x >= hp[0][1]:
heapq.heappop(hp)
if negH: heapq.heappush(hp, (negH, R))
if res[-1][1] + hp[0][0]:
res += [x, -hp[0][0]],
return res[1:]
public class Solution {
public List
getSkyline(int[][] buildings) {
List
result = new ArrayList
();
if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
return result;
}
List
heights = new ArrayList
();
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
() {
@Override
public int compare(Height h1, Height h2) {
return h1.index != h2.index ? h1.index - h2.index : h1.height - h2.height;
}
});
PriorityQueue
pq = new PriorityQueue
(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;
}
}
}
