乐趣区

关于后端:综合笔试题难度-455扫描线的特殊运用详尽答疑

jiezi

题目形容

这是 LeetCode 上的 218. 天际线问题 ，难度为 艰难。

Tag :「扫描线问题」、「优先队列（堆）」

城市的天际线是从远处观看该城市中所有建筑物造成的轮廓的内部轮廓。给你所有建筑物的地位和高度，请返回由这些建筑物造成的 天际线。

每个建筑物的几何信息由数组 buildings 示意，其中三元组 buildings[i] = [lefti, righti, heighti] 示意：

  • left[i] 是第 i 座建筑物左边缘的 x 坐标。
  • right[i] 是第 i 座建筑物右边缘的 x 坐标。
  • height[i] 是第 i 座建筑物的高度。

天际线 应该示意为由“关键点”组成的列表，格局 [[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 <= buildings.length <= 10^4$
  • $0 <= lefti < righti <= 2^{31} – 1$
  • $1 <= heighti <= 2^{31} – 1$
  • buildings 按 $left_i$ 非递加排序

根本剖析

这是一题特地的扫描线问题 🤣🤣🤣

既不是求周长，也不是求面积，是求轮廓中的所有的水平线的左端点 🤣🤣🤣

所以这不是一道必须用「线段树」来解决的扫描线问题（因为不须要思考区间查问问题）。

扫描线的外围在于 将不规则的形态依照程度或者垂直的形式，划分成若干个规定的矩形。

扫描线

对于本题，对应的扫描线宰割形态如图：

不难发现，由相邻两个横坐标以及最大高度，能够确定一个矩形。

题目要咱们 输入每个矩形的“上边”的左端点，同时跳过可由前一矩形“上边”延展而来的那些边。

因而咱们须要实时保护一个最大高度，能够应用优先队列（堆）。

实现时，咱们能够先记录下 $buildings$ 中所有的左右端点横坐标及高度，并依据端点横坐标进行从小到大排序。

在从前往后遍历解决时（遍历每个矩形），依据以后遍历到的点进行分状况探讨：

  • 左端点：因为是左端点，必然存在一条从右延展的边，但不肯定是须要被记录的边，因为在同一矩形中，咱们只须要记录最上边的边。这时候能够将高度进行入队；
  • 右端点：此时意味着之前某一条往右延展的线完结了，这时候须要将高度出队（代表这完结的线不被思考）。

而后从优先队列中取出以后的最大高度，为了避免以后的线与前一矩形“上边”延展而来的线重合，咱们须要应用一个变量 prev 记录上一个记录的高度。

代码：

class Solution {public List<List<Integer>> getSkyline(int[][] bs) {List<List<Integer>> ans = new ArrayList<>();
        
        // 预处理所有的点，为了不便排序，对于左端点，令高度为负；对于右端点令高度为正
        List<int[]> ps = new ArrayList<>();
        for (int[] b : bs) {int l = b[0], r = b[1], h = b[2];
            ps.add(new int[]{l, -h});
            ps.add(new int[]{r, h});
        }

        // 先依照横坐标进行排序
        // 如果横坐标雷同，则依照左端点排序
        // 如果雷同的左 / 右端点，则依照高度进行排序
        Collections.sort(ps, (a, b)->{if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        
        // 大根堆
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int prev = 0;
        q.add(prev);
        for (int[] p : ps) {int point = p[0], height = p[1];
            if (height < 0) {
                // 如果是左端点，阐明存在一条往右延长的可记录的边，将高度存入优先队列
                q.add(-height);
            } else {
                // 如果是右端点，阐明这条边完结了，将以后高度从队列中移除
                q.remove(height);
            }

            // 取出最高高度，如果以后不与前一矩形“上边”延展而来的那些边重合，则能够被记录
            int cur = q.peek();
            if (cur != prev) {List<Integer> list = new ArrayList<>();
                list.add(point);
                list.add(cur);
                ans.add(list);
                prev = cur;
            }
        }
        return ans;
    }
}
  • 工夫复杂度：须要解决的矩阵数量与 $n$ 反比，每个矩阵须要应用优先队列保护高度，其中 remove 操作须要先破费 $O(n)$ 复杂度进行查找，而后通过 $O(\log{n})$ 复杂度进行移除，复杂度为 $O(n)$。整体复杂度为 $O(n^2)$
  • 空间复杂度：$O(n)$

答疑

1. 将左端点的高度存成正数再进行排序是什么意思？

这里只是为了不便，所以采取了这样的做法，当然也可能多应用一位来代指「左右」。

只有最终能够达到如下的排序规定即可：

  1. 先严格依照横坐标进行「从小到大」排序

  2. 对于某个横坐标而言，可能会同时呈现多个点，该当依照如下规定进行解决：

    1. 优先解决左端点，再解决右端点
    2. 如果同样都是左端点，则依照高度「从大到小」进行解决（将高度减少到优先队列中）
    3. 如果同样都是右端点，则依照高度「从小到大」进行解决（将高度从优先队列中删掉）

代码：

class Solution {public List<List<Integer>> getSkyline(int[][] bs) {List<List<Integer>> ans = new ArrayList<>();
        List<int[]> ps = new ArrayList<>();
        for (int[] b : bs) {int l = b[0], r = b[1], h = b[2];
            ps.add(new int[]{l, h, -1});
            ps.add(new int[]{r, h, 1});
        }
        /**
         * 先严格依照横坐标进行「从小到大」排序
         * 对于某个横坐标而言，可能会同时呈现多个点，该当依照如下规定进行解决：* 1. 优先解决左端点，再解决右端点
         * 2. 如果同样都是左端点，则依照高度「从大到小」进行解决（将高度减少到优先队列中）* 3. 如果同样都是右端点，则依照高度「从小到大」进行解决（将高度从优先队列中删掉）*/
        Collections.sort(ps, (a, b)->{if (a[0] != b[0]) return a[0] - b[0];
            if (a[2] != b[2]) return a[2] - b[2];
            if (a[2] == -1) {return b[1] - a[1];
            } else {return a[1] - b[1];
            }
        });
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int prev = 0;
        q.add(prev);
        for (int[] p : ps) {int point = p[0], height = p[1], flag = p[2];
            if (flag == -1) {q.add(height);
            } else {q.remove(height);
            }

            int cur = q.peek();
            if (cur != prev) {List<Integer> list = new ArrayList<>();
                list.add(point);
                list.add(cur);
                ans.add(list);
                prev = cur;
            }
        }
        return ans;
    }
}

2. 为什么在解决前，先往「优先队列」增加一个 $0$？

因为题目自身要求咱们把一个残缺轮廓的「右下角」那个点也取到，所以须要先增加一个 $0$。

也就是下图被圈进去的那些点：

3. 优先队列的 remove 操作成为了瓶颈，如何优化？

因为优先队列的 remove 操作须要先通过 $O(n)$ 的复杂度进行查找，再通过 $O(\log{n})$ 的复杂度进行删除。因而整个 remove 操作的复杂度是 $O(n)$ 的，这导致了咱们算法整体复杂度为 $O(n^2)$。

优化形式包含：应用基于红黑树的 TreeMap 代替优先队列；或是应用「哈希表」记录「执行了删除操作的高度」及「删除次数」，在每次应用前先查看堆顶高度是否曾经被标记删除，如果是则进行 poll 操作，并更新删除次数，直到遇到一个没被删除的堆顶高度。

代码：

class Solution {public List<List<Integer>> getSkyline(int[][] bs) {List<List<Integer>> ans = new ArrayList<>();
        List<int[]> ps = new ArrayList<>();
        for (int[] b : bs) {int l = b[0], r = b[1], h = b[2];
            ps.add(new int[]{l, h, -1});
            ps.add(new int[]{r, h, 1});
        }
        /**
         * 先严格依照横坐标进行「从小到大」排序
         * 对于某个横坐标而言，可能会同时呈现多个点，该当依照如下规定进行解决：* 1. 优先解决左端点，再解决右端点
         * 2. 如果同样都是左端点，则依照高度「从大到小」进行解决（将高度减少到优先队列中）* 3. 如果同样都是右端点，则依照高度「从小到大」进行解决（将高度从优先队列中删掉）*/
        Collections.sort(ps, (a, b)->{if (a[0] != b[0]) return a[0] - b[0];
            if (a[2] != b[2]) return a[2] - b[2];
            if (a[2] == -1) {return b[1] - a[1];
            } else {return a[1] - b[1];
            }
        });
        // 记录进行了删除操作的高度，以及删除次数
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int prev = 0;
        q.add(prev);
        for (int[] p : ps) {int point = p[0], height = p[1], flag = p[2];
            if (flag == -1) {q.add(height);
            } else {map.put(height, map.getOrDefault(height, 0) + 1);
            }

            while (!q.isEmpty()) {int peek = q.peek();
                if (map.containsKey(peek)) {if (map.get(peek) == 1) map.remove(peek);
                    else map.put(peek, map.get(peek) - 1);
                    q.poll();} else {break;}
            }

            int cur = q.peek();
            if (cur != prev) {List<Integer> list = new ArrayList<>();
                list.add(point);
                list.add(cur);
                ans.add(list);
                prev = cur;
            }
        }
        return ans;
    }
}
  • 工夫复杂度：$O(n\log{n})$
  • 空间复杂度：$O(n)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.218 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版