天际线问题
2023-12-21 14:41:30
题目链接
题目描述
注意点
- 可以假设所有的建筑都是完美的长方形,在高度为 0 的绝对平坦的表面上
- 输出天际线中不得有连续的相同高度的水平线
- buildings 按 lefti 非递减排序
解答思路
- 矩形会有重叠部分,当多个矩形重合时,取高度最高的矩形,如示例一中的图B所示,本题关键是要找到转换为图B后的每个矩形的左侧端点及高度
- 参考题解使用扫描线+优先队列解决,扫描线使用竖线,将初始每个矩阵的左右端点使用扫描线标记,为了方便后续排序,将左端点对应的高度设置为负数,后续排序的规则为:左端点比右端点优先,如果都是左端点/右端点,则将高度更高的端点优先,保证按顺序遍历扫描线,同时如果多个矩形的扫描线重合时更高的矩形也能包住更低的矩形
- 随后使用优先队列找到关键点,在访问到左端点时入栈,访问到右端点时其对应的矩形已到尽头,需要出栈,优先队列始终保证队首的元素为当前所有覆盖的矩形中的最高高度,如果最高高度相比上一次关键点发生了变化,则需要将当前的关键点加入到结果集中,并更新上一次关键点为当前关键点
代码
class Solution {
public List<List<Integer>> getSkyline(int[][] bs) {
List<List<Integer>> res = new ArrayList<>();
int n = bs.length;
// 存储一个端点的(x, y),如果是左端点则y为负数,右端点则y为整数,方便排序
List<int[]> xyList = new ArrayList<>(n * 2);
for (int i = 0; i < n; i++) {
int left = bs[i][0];
int right = bs[i][1];
int height = bs[i][2];
int[] leftPoint = {left, -height};
int[] rightPoint = {right, height};
xyList.add(leftPoint);
xyList.add(rightPoint);
}
// 从小到大排序
Collections.sort(xyList, (a, b) -> {
// 如果x值不同,则直接按x值进行排序,保证从左到右访问端点
if (a[0] != b[0]) {
return a[0] - b[0];
}
// 如果x值相同,由于前面左端点处设置y值为负数,所以一定保证左端点优先
// 如果x值相同,且都是左端点,则也是按照y进行排序,高度高的优先
// 如果x值相同,且都是右端点,则也是按照y进行排序,高度低的优先
// 保证更高的矩形始终将高度低的矩形包在里面
return a[1] - b[1];
});
// 优先队列保证最大高度始终在队列顶端
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (b - a));
queue.add(0);
int prevHeight = 0;
for (int[] point : xyList) {
int x = point[0];
int y = point[1];
if (y < 0) {
// 左端点入队列
queue.add(-y);
} else {
// 右端点出队列
queue.remove(y);
}
int maxHeight = queue.peek();
// 最大高度发生变化,将新矩阵的左端点及高度写入结果
if (prevHeight != maxHeight) {
List<Integer> sonRes = new ArrayList<>(2);
sonRes.add(x);
sonRes.add(maxHeight);
res.add(sonRes);
// 设置前置高度,保证跳过同一高度的相连矩形
prevHeight = maxHeight;
}
}
return res;
}
}
关键点
- 扫描线的思想(本题存储二元数组(x, y),x为横坐标值,y为纵坐标值,也是高度)
- 优先队列的使用
- 将左端点的高度都设置为负数保证左端点始终优先于右端点
文章来源:https://blog.csdn.net/weixin_51628158/article/details/135100887
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!