原题传送门

1. 题目描述

2. Solution 1

1、思路分析

观察发现，关键点的横坐标总是落在建筑的左右边缘上。这样可以只考虑每一座建筑的边缘作为横坐标，其对应的纵坐标为“包含该横坐标”的所有建筑的最大高度。

观察示例一可以发现，当关键点为某建筑的右边缘时，该建筑的高度对关键点的纵坐标是没有贡献的。如，图中横坐标为7的关键点，虽然它落在红色建筑的右边缘，但红色建筑对其并纵坐标并没有贡献。因此给出“包含该横坐标”的定义: 建筑的左边缘小于等于该横坐标，右边缘大于该横坐标(也就是不考虑建筑的右边缘)。即对于包含横坐标的建筑，有。(The basic idea of this solutions is to find the critical points that change the max height among the buildings on the left)

特别地，在部分情况下，“包含该横坐标”的建筑并不存在。如当图只有一座建筑时，该建筑的左右边缘均对应一个关键点，当横坐标为其右边缘时，这唯一的建筑对其纵坐标没有贡献。因此该横坐标对应的纵坐标的大小为0。

由上面的分析，可以得到一个暴力算法：O(n)地枚举建筑的每一个边缘作为关键点的横坐标，过程中O(n)地检查每一座建筑是否“包含该横坐标”，找到最大高度，即为该关键点的纵坐标。该算法的时间复杂度是O(n^2)，需要进行优化。

可以用优先队列来优化寻找最大高度的时间，在从左到右枚举横坐标的过程中，实时地更新该优先队列即可。这样无论何时，优先队列的队首元素即为最大高度。为了维护优先队列，需要使用“延迟删除”的技巧，即无需每次横坐标改变就立刻将优先队列中所有不符合条件的元素都删除，而只需要保证优先队列的队首元素“包含该横坐标”即可。

2、代码实现

package Q0299.Q0218TheSkylineProblem;
import java.util.*;
// The basic idea of this solutions is to find the critical points that change the max height among the buildings on
// the left
public class Solution {
public List> getSkyline(int[][] buildings) {
List> res = new ArrayList<>();
List height = new ArrayList<>(); // height list to store all buildings' heights
for (int[] b : buildings) {
height.add(new int[]{b[0], -b[2]}); // start of a building, height stored as negtive
height.add(new int[]{b[1], b[2]}); // end of a building, height stored as positive
}
Collections.sort(height, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0])); // sort the height list
// a pq that stores all the encountered buildings' heights in descending order
PriorityQueue pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
int preMax = 0;
for (int[] h : height) {
if (h[1] <0) { // h[1] <0, that means it meets a new building, so add it to pq
pq.offer(-h[1]);
} else { // h[1] >=0, that means it has reached the end of the building, so remove it from pq
pq.remove(h[1]);
}
// the current max height in all encountered buildings
int curMax = pq.peek();
// if the max height is different from the previous one, that means a critical point is met, add to result list
if (curMax != preMax) {
res.add(Arrays.asList(h[0], curMax));
preMax = curMax;
}
}
return res;
}
}


3、复杂度分析

时间复杂度: O(n log n)

空间复杂度: O(n)