题目描述
这是 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],[3,2,4,4]] 输出：false 解释：图形顶端留有空缺，无法覆盖成一个矩形。 复制代码
示例 4：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]] 输出：false 解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。 复制代码
提示：
- 1 <= rectangles.length <= 2 * 10^41<=rectangles.length<=2∗104
- rectangles[i].length == 4
- -10^5 <= xi, yi, ai, bi <= 10^5−105<=xi,yi,ai,bi<=105
扫描线
将每个矩形 rectangles[i]rectangles[i] 看做两条竖直方向的边，使用 (x, y1, y2)(x,y1,y2) 的形式进行存储（其中 y1y1 代表该竖边的下端点，y2y2 代表竖边的上端点），同时为了区分是矩形的左边还是右边，再引入一个标识位，即以四元组 (x, y1, y2, flag)(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)；对边集进行排序的复杂度为 O(n\log{n})O(nlogn)，对排序好的边集进行遍历检查，每条边会被扫描线性次，复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn) - 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.391 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
