LeetCode 391 完美矩形

在做矩形覆盖的题目时，很多人第一反应就是「遍历 + 合并区间」，但 LeetCode 的完美矩形题目可没那么简单。它不仅要求所有小矩形刚好拼出一个大矩形，而且不能有重叠、不能有缝隙，就像拼图一样必须严丝合缝。本文会带你逐步拆解问题，分析为什么简单的遍历不够用，并给出一个基于面积校验 + 顶点校验的高效解法。

Swift社区

803人浏览 · 2025-09-29 09:13:18

Swift社区 · 2025-09-29 09:13:18 发布

在这里插入图片描述

文章目录

摘要

在做矩形覆盖的题目时，很多人第一反应就是「遍历 + 合并区间」，但 LeetCode 的 完美矩形 题目可没那么简单。它不仅要求所有小矩形刚好拼出一个大矩形，而且不能有重叠、不能有缝隙，就像拼图一样必须严丝合缝。本文会带你逐步拆解问题，分析为什么简单的遍历不够用，并给出一个基于 面积校验 + 顶点校验 的高效解法。

描述

题目给你一组小矩形，每个矩形由左下角 (xi, yi) 和右上角 (ai, bi) 表示，矩形都是和坐标轴平行的。现在你要判断这些矩形是否能 完美拼接成一个更大的矩形。

判断标准主要有两个：

拼接后的整体区域必须是一个完整的大矩形。
小矩形之间不能重叠，也不能留下空隙。

换句话说，我们不仅要保证拼出来的总面积等于大矩形的面积，还要保证小矩形的边界刚好吻合。

实际场景类比：
可以想象一下装修时铺瓷砖：如果你要用一堆小方砖铺满一个长方形的地板，那么这堆砖必须正好覆盖整个地板，不能多也不能少，更不能有两块砖重叠。

题解答案

核心思路是 面积校验 + 顶点唯一性：

面积校验：所有小矩形的面积和必须等于大矩形的面积。
顶点校验：大矩形的四个顶点必须只出现一次，其它所有中间拼接的点必须出现偶数次（因为它们会被相邻矩形共享）。

一旦两个条件同时满足，就说明所有矩形能完美拼成一个大矩形。

题解代码分析

下面是完整的 Swift 实现代码：

import Foundation

class PerfectRectangle {
    func isRectangleCover(_ rectangles: [[Int]]) -> Bool {
        var minX = Int.max, minY = Int.max
        var maxX = Int.min, maxY = Int.min
        var areaSum = 0
        var points = Set<String>()
        
        func addOrRemovePoint(_ x: Int, _ y: Int) {
            let key = "\(x),\(y)"
            if points.contains(key) {
                points.remove(key)
            } else {
                points.insert(key)
            }
        }
        
        for rect in rectangles {
            let x1 = rect[0], y1 = rect[1]
            let x2 = rect[2], y2 = rect[3]
            
            // 更新外接矩形边界
            minX = min(minX, x1)
            minY = min(minY, y1)
            maxX = max(maxX, x2)
            maxY = max(maxY, y2)
            
            // 累加面积
            areaSum += (x2 - x1) * (y2 - y1)
            
            // 处理矩形四个顶点
            addOrRemovePoint(x1, y1)
            addOrRemovePoint(x1, y2)
            addOrRemovePoint(x2, y1)
            addOrRemovePoint(x2, y2)
        }
        
        // 计算外接矩形的面积
        let expectedArea = (maxX - minX) * (maxY - minY)
        if areaSum != expectedArea {
            return false
        }
        
        // 外接矩形的四个顶点
        let expectedPoints = [
            "\(minX),\(minY)",
            "\(minX),\(maxY)",
            "\(maxX),\(minY)",
            "\(maxX),\(maxY)"
        ]
        
        // 校验点集合是否只剩下四个顶点
        if points.count != 4 {
            return false
        }
        
        for p in expectedPoints {
            if !points.contains(p) {
                return false
            }
        }
        
        return true
    }
}

代码解析

边界计算：通过遍历所有矩形，记录整个覆盖区域的最小 (x, y) 和最大 (x, y)，得到大矩形的外接边界。
面积验证：小矩形的面积总和必须和外接矩形的面积一致。
顶点处理：
- 对每个小矩形的四个顶点执行「异或」式的操作：如果顶点第一次出现就加入集合，如果再次出现就删除。
- 最终应该只剩下外接矩形的四个顶点。
返回结果：如果面积对上，顶点集合正确，就返回 true。

示例测试及结果

let solver = PerfectRectangle()

print(solver.isRectangleCover([[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]))
// 输出: true

print(solver.isRectangleCover([[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]))
// 输出: false

print(solver.isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]))
// 输出: false