☆打卡算法☆LeetCode 218. 天际线问题 算法解析
☆打卡算法☆LeetCode 218. 天际线问题 算法解析
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定所有建筑物的位置和高度，返回这些建筑物形成的天际线。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。
每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
- lefti 是第 i 座建筑物左边缘的 x 坐标。
- righti 是第 i 座建筑物右边缘的 x 坐标。
- heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。
天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]
示例 1：
输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。示例 2：
输入： buildings = [[0,2,3],[2,5,3]]
输出： [[0,3],[5,0]]二、解题
1、思路分析
根据题意可以得知，天际线其实就是由关键点组成的列表，按照x坐标进行排序，关键点是水平线段的左右端点。
因为关键点总是落在建筑的左右端点上，当最大高度发生变化时，会遇到一个新的关键点，也就是一个直线永远在最高的楼上，高度发生变化，天际线会产生一条心的线段起点，也就是一个关键点。
接着，就是需要用一个数据结构来记录从左到右扫描过程中当前高度的变化情况。
在遍历过程中：
- 遇到左端点，加入对应的高度，也就是最高横坐标
- 遇到右端点，删除对应的高度，也就是不是最高横坐标
- 查找要删除的高度进行删除
然后判断在进行此操作之后，天际线的最大高度是否改变。
最大高度一旦变化，则需要往答案中添加一个新的关键点。
2、代码实现
代码参考：
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
List<Integer> boundaries = new ArrayList<Integer>();
for (int[] building : buildings) {
boundaries.add(building[0]);
boundaries.add(building[1]);
}
Collections.sort(boundaries);
List<List<Integer>> ret = new ArrayList<List<Integer>>();
int n = buildings.length, idx = 0;
for (int boundary : boundaries) {
while (idx < n && buildings[idx][0] <= boundary) {
pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
idx++;
}
while (!pq.isEmpty() && pq.peek()[0] <= boundary) {
pq.poll();
}
int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
if (ret.size() == 0 || maxn != ret.get(ret.size() - 1).get(1)) {
ret.add(Arrays.asList(boundary, maxn));
}
}
return ret;
}
}
3、时间复杂度
时间复杂度：O(n log n)
其中n为建筑数量，每个建筑至多只需要入队与出队一次，单词时间复杂度为O(log n)。
空间复杂度：O(n)
其中n为建筑数量。
三、总结
代码实现的过程中用到了一个队列。
然后按顺序枚举横坐标，用数组boundaries保存所有的边缘，排序后遍历该数组。
遇到包含横坐标的建筑加入到优先队列中，不断检查优先队列中的队首元素是否包含该横坐标。
如果不包含该横坐标，就将队首元素弹出队列，直到队空或队首元素包含该横坐标即可。