天际线问题

发布时间:2023年12月21日

题目链接

天际线问题

题目描述


注意点

  • 可以假设所有的建筑都是完美的长方形,在高度为 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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。