LeetCode 218 - The Skyline Problem

作者 QIFAN 日期 2017-01-29
LeetCode 218 - The Skyline Problem

原题链接: 218. The Skyline Problem


题干

用两个坐标代表一栋建筑的两个顶点,给定这样一串建筑,返回他们的边界点。边界点是指轮廓中所有左端点的坐标。建筑已按左顶点排序。

思路

做不出来,看的讨论。
代码参考:https://discuss.leetcode.com/topic/22482/short-java-solution

建议思路先看三哥这个视频,比较清楚:




自己再总结一下:

  • 先将建筑转换为 (x, y) 形式的坐标集合 list ,并按照 x 升序排序
  • 使用一个 PriorityQueue pq 存储当前所在建筑群的高度
  • 对于 list[i]
    • 如果 pq 中不存在 list[i][1] ,说明这是扫到了某个建筑的左边界,将高度存入 pq
    • 如果 pq 中存在,说明某个建筑扫描完毕,将此高度移除
  • 此时检查当前最大高度,若高度发生了变化,说明刚才插入的建筑比之前的高,或是最高的建筑完了和下面的一个建筑相交了,这就是交点,所以往结果中添加 list[i][0], pq.peek()

时间复杂度分析:

  • 转换坐标 $O(N)$
  • 排序 $O(NlogN)$
  • 遍历 $O(N)$ ,其中 PQ 插入 worst case 为 $O(logN)$ ,所以一共 $O(NlogN)$

综上总计 $O(NlogN)$

代码:

public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
List<int[]> height = new ArrayList<>();
// 转换坐标
for(int[] b:buildings) {
height.add(new int[]{b[0], -b[2]});
height.add(new int[]{b[1], b[2]});
}
// 坐标排序
Collections.sort(height, (a, b) -> {
if(a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
});
Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0); // 初始高度为 0
int prev = 0;
for(int[] h:height) {
if(h[1] < 0) {
pq.offer(-h[1]); // 建筑的左边,首次扫到该建筑
} else {
pq.remove(h[1]); // 建筑的右边
}
int cur = pq.peek();
if(prev != cur) { // 最大高度发生了改变
result.add(new int[]{h[0], cur});
prev = cur;
}
}
return result;
}