218 The Skyline Problem
218. The Skyline Problem
题目: 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到结果中。
参考Brian Gordon的blog 和 Stefan大神的题解
程序代码解释
- 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
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<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;
}
}
}
Author: Keqi Huang
If you like it, please spread your support
