文章目录摘要描述题解答案题解代码分析外包矩形与面积角点翻转奇偶性最终判断示例 1 简要过程示例测试及结果示例 1示例 2示例 3时间复杂度空间复杂度实际应用场景总结摘要这道题要求判断若干个小矩形能否「精确覆盖」一个矩形区域既不能有空隙也不能有重叠。听起来像几何题但核心是两条数学条件加一个「角点奇偶性」技巧。思路可以归纳为先算出所有矩形的外包矩形以及面积和若小矩形面积之和不等于外包矩形面积一定不可能是完美覆盖再用「角点集合」做校验——每个小矩形的四个顶点按“出现就翻转”的方式加入集合最后集合里必须恰好剩下外包矩形的四个角点。这样就能在 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^4rectangles[i].length 4-10^5 xi ai 10^5-10^5 yi bi 10^5核心思路一是面积必须对上二是用角点的「出现奇数次」来刻画「只出现在最终边界上的点」——最终边界上的点只会被覆盖一次内部或边缘上的交点会被相邻矩形共享出现偶数次用集合翻转后会被消掉最后只剩外包矩形的四个角。题解答案classSolution{funcisRectangleCover(_rectangles:[[Int]])-Bool{varminXInt.max,minYInt.maxvarmaxXInt.min,maxYInt.minvartotalArea0varcornerSetSetString()forrectinrectangles{letx1rect[0],y1rect[1],x2rect[2],y2rect[3]minXmin(minX,x1)minYmin(minY,y1)maxXmax(maxX,x2)maxYmax(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:SetString[\(minX),\(minY),\(minX),\(maxY),\(maxX),\(minY),\(maxX),\(maxY)]returncornerSetexpected}}题解代码分析外包矩形与面积遍历时维护所有矩形的最小左下角(minX, minY)和最大右上角(maxX, maxY)得到外包矩形。同时累加每个矩形的面积(x2-x1)*(y2-y1)。若存在空隙或重叠小矩形面积之和一定不等于外包矩形面积(maxX-minX)*(maxY-minY)因此先做这一步可以快速排除大部分非法情况。角点翻转奇偶性每个矩形有四个顶点。在精确覆盖下最终大矩形的四个角点只被一个小矩形覆盖只出现 1 次。大矩形边上非角的点被两个小矩形共享出现 2 次。大矩形内部的点被 2 或 4 个小矩形共享出现 2 或 4 次。用集合做「出现就翻转」第一次出现则加入集合第二次出现则从集合移除。这样出现偶数次的点最后都不会在集合里只有出现奇数次的点会留下。精确覆盖时只会剩下大矩形的四个角点。对每个矩形把四个顶点用字符串x,y表示依次做「在集合中则删否则加」即可。Swift 里SetString可以满足去重和查找。最终判断若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]]外包minX1, minY1, maxX4, maxY4面积9。小矩形面积和412119面积一致。角点翻转后集合中应只剩 (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 是否恰好填满父视图、没有空隙或重叠也可以抽象成同样的问题。用面积加角点奇偶性可以在不逐像素检查的情况下快速判断适合数据量较大的场景。总结完美矩形的判断依赖两点面积相等 角点奇偶性。用「角点翻转集合」可以在不枚举格点的前提下判断是否恰好覆盖成一个大矩形思路简洁、实现简单适合作为几何覆盖类题目的模板写法。