当前位置：首页 > news >正文

详细介绍：LeetCode 391 完美矩形

news 2025/10/4 10:25:32

详细介绍：LeetCode 391 完美矩形

在这里插入图片描述

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 代码解析
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结

摘要

在做矩形覆盖的题目时，很多人第一反应就是「遍历 + 合并区间」，但 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