LeetCode 391 完美矩形 - Swift 题解

摘要

这道题要求判断若干个小矩形能否「精确覆盖」一个矩形区域：既不能有空隙，也不能有重叠。听起来像几何题，但核心是两条数学条件加一个「角点奇偶性」技巧。

思路可以归纳为：先算出所有矩形的外包矩形以及面积和；若小矩形面积之和不等于外包矩形面积，一定不可能是完美覆盖；再用「角点集合」做校验——每个小矩形的四个顶点按“出现就翻转”的方式加入集合，最后集合里必须恰好剩下外包矩形的四个角点。这样就能在 O(n) 时间内判断，无需真的去铺格子。下面用 Swift 实现并说明细节。

描述

给你一个数组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 * 10^4
• rectangles[i].length == 4
• -10^5 <= xi < ai <= 10^5
• -10^5 <= yi < bi <= 10^5

核心思路：一是面积必须对上；二是用角点的「出现奇数次」来刻画「只出现在最终边界上的点」——最终边界上的点只会被覆盖一次，内部或边缘上的交点会被相邻矩形共享，出现偶数次，用集合翻转后会被消掉，最后只剩外包矩形的四个角。

题解答案

classSolution{funcisRectangleCover(_rectangles:[[Int]])->Bool{varminX=Int.max,minY=Int.maxvarmaxX=Int.min,maxY=Int.minvartotalArea=0varcornerSet=Set<String>()forrectinrectangles{letx1=rect[0],y1=rect[1],x2=rect[2],y2=rect[3]minX=min(minX,x1)minY=min(minY,y1)maxX=max(maxX,x2)maxY=max(maxY,y2)totalArea+=(x2-x1)*(y2-y1)letcorners=["\(x1),\(y1)","\(x1),\(y2)","\(x2),\(y1)","\(x2),\(y2)"]forcincorners{ifcornerSet.contains(c){cornerSet.remove(c)}else{cornerSet.insert(c)}}}letboundingArea=(maxX-minX)*(maxY-minY)iftotalArea!=boundingArea{returnfalse}letexpected:Set<String>=["\(minX),\(minY)","\(minX),\(maxY)","\(maxX),\(minY)","\(maxX),\(maxY)"]returncornerSet==expected}}

题解代码分析

外包矩形与面积

遍历时维护所有矩形的最小左下角(minX, minY)和最大右上角(maxX, maxY)，得到外包矩形。同时累加每个矩形的面积(x2-x1)*(y2-y1)。

若存在空隙或重叠，小矩形面积之和一定不等于外包矩形面积(maxX-minX)*(maxY-minY)，因此先做这一步可以快速排除大部分非法情况。

角点翻转（奇偶性）

每个矩形有四个顶点。在精确覆盖下：

• 最终大矩形的四个角点：只被一个小矩形覆盖，只出现 1 次。
• 大矩形边上（非角）的点：被两个小矩形共享，出现 2 次。
• 大矩形内部的点：被 2 或 4 个小矩形共享，出现 2 或 4 次。

用集合做「出现就翻转」：第一次出现则加入集合，第二次出现则从集合移除。这样出现偶数次的点最后都不会在集合里，只有出现奇数次的点会留下。精确覆盖时，只会剩下大矩形的四个角点。

对每个矩形，把四个顶点用字符串"x,y"表示，依次做「在集合中则删，否则加」即可。Swift 里Set<String>可以满足去重和查找。

最终判断

• 若totalArea != boundingArea，直接返回false。
• 否则看cornerSet是否恰好等于由(minX,minY),(minX,maxY),(maxX,minY),(maxX,maxY)组成的四个点的集合。是则true，否则false。

示例 1 简要过程

rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
外包：minX=1, minY=1, maxX=4, maxY=4，面积=9。小矩形面积和=4+1+2+1+1=9，面积一致。
角点翻转后，集合中应只剩 (1,1),(1,4),(4,1),(4,4)，对应 true。

示例测试及结果

示例 1

输入：[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
面积和=外包面积=9，角点集合为四个外包角点 →true。

示例 2

输入：[[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
中间有缝，小矩形面积和会小于外包面积（或角点集合不等于四个角） →false。

示例 3

输入：[[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
有重叠，小矩形面积和会大于外包面积（或角点集合不是恰好四个角） →false。

时间复杂度

遍历所有矩形一次：计算外包、面积和、角点翻转。矩形条数为 n，每条 4 个顶点，集合操作 O(1)，总时间O(n)。

空间复杂度

角点集合最多约 4n 个不同字符串（实际远少于 4n，因为很多点会成对消掉）。最坏O(n)。外包与面积等为 O(1)。

实际应用场景

这类「精确覆盖」判断在实际里也会碰到。比如地图或 CAD 里，用多个矩形块去铺满一个区域时，需要检查是否铺满且无重叠；再比如 UI 布局里，若干子视图的 frame 是否恰好填满父视图、没有空隙或重叠，也可以抽象成同样的问题。用面积加角点奇偶性，可以在不逐像素检查的情况下快速判断，适合数据量较大的场景。

总结

完美矩形的判断依赖两点：面积相等 + 角点奇偶性。用「角点翻转集合」可以在不枚举格点的前提下，判断是否恰好覆盖成一个大矩形，思路简洁、实现简单，适合作为几何覆盖类题目的模板写法。