题目形容

这是 LeetCode 上的 391. 完满矩形 ，难度为 艰难。

Tag : 「扫描线」

给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 示意一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。

如果所有矩形一起准确笼罩了某个矩形区域，则返回 true ；否则，返回 false 。

 
示例 1：

输出：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]输入：true解释：5 个矩形一起能够准确地笼罩一个矩形区域。

示例 2：

输出：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]输入：false解释：两个矩形之间有距离，无奈笼罩成一个矩形。

示例 3：

输出：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]输入：false解释：因为两头有相交区域，尽管造成了矩形，但不是准确笼罩。

提醒：

  • $1 <= rectangles.length <= 2 \times 10^4$
  • $rectangles[i].length = 4$
  • $-10^5 <= x_i, y_i, a_i, b_i <= 10^5$

扫描线

将每个矩形 $rectangles[i]$ 看做两条竖直方向的边，应用 $(x, y1, y2)$ 的模式进行存储（其中 $y1$ 代表该竖边的下端点，$y2$ 代表竖边的上端点），同时为了辨别是矩形的右边还是左边，再引入一个标识位，即以四元组 $(x, y1, y2, flag)$ 的模式进行存储。

一个完满矩形的充要条件为：对于完满矩形的每一条非边缘的竖边，都「成对」呈现（存在两条完全相同的右边和左边重叠在一起）；对于完满矩形的两条边缘竖边，均独立为一条间断的（不重叠）的竖边。

如图（红色框的为「完满矩形的边缘竖边」，绿框的为「完满矩形的非边缘竖边」）：

  • 绿色：非边缘竖边必然有成对的左右两条完全相同的竖边重叠在一起；
  • 红色：边缘竖边因为只有单边，必然不重叠，且连接成一条实现的竖边。

代码：

class Solution {    public boolean isRectangleCover(int[][] rectangles) {        int n = rectangles.length;        int[][] rs = new int[n * 2][4];        for (int i = 0, idx = 0; i < n; i++) {            int[] re = rectangles[i];            rs[idx++] = new int[]{re[0], re[1], re[3], 1};            rs[idx++] = new int[]{re[2], re[1], re[3], -1};        }        Arrays.sort(rs, (a,b)->{            if (a[0] != b[0]) return a[0] - b[0];            return a[1] - b[1];        });        n *= 2;        // 别离存储雷同的横坐标下「右边的线段」和「左边的线段」 (y1, y2)        List<int[]> l1 = new ArrayList<>(), l2 = new ArrayList<>();         for (int l = 0; l < n; ) {            int r = l;            l1.clear(); l2.clear();            // 找到横坐标雷同局部            while (r < n && rs[r][0] == rs[l][0]) r++;            for (int i = l; i < r; i++) {                int[] cur = new int[]{rs[i][1], rs[i][2]};                List<int[]> list = rs[i][3] == 1 ? l1 : l2;                if (list.isEmpty()) {                    list.add(cur);                } else {                    int[] prev = list.get(list.size() - 1);                    if (cur[0] < prev[1]) return false; // 存在重叠                    else if (cur[0] == prev[1]) prev[1] = cur[1]; // 首尾相连                    else list.add(cur);                 }            }            if (l > 0 && r < n) {                // 若不是完满矩形的边缘竖边，查看是否成对呈现                if (l1.size() != l2.size()) return false;                for (int i = 0; i < l1.size(); i++) {                    if (l1.get(i)[0] == l2.get(i)[0] && l1.get(i)[1] == l2.get(i)[1]) continue;                    return false;                }            } else {                // 若是完满矩形的边缘竖边，查看是否造成残缺一段                if (l1.size() + l2.size() != 1) return false;            }            l = r;        }        return true;    }}
  • 工夫复杂度：将 rectangles 划分成边集的复杂度为 $O(n)$；对边集进行排序的复杂度为 $O(n\log{n})$，对排序好的边集进行遍历查看，每条边会被扫描线性次，复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
  • 空间复杂度：$O(n)$

最初

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

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

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

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

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

本文由mdnice多平台公布