设计完美矩形 题目描述 给你一个数组 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 解释：这五个矩形恰好覆盖了一个从 (1,1) 到 (4,4) 的矩形区域。 示例 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 解释：矩形 (3,2,4,4) 与矩形 (3,1,4,2) 在点 (3,2) 处有一个重叠。 解题过程循序渐进讲解 第一步：理解问题与核心条件 “完美矩形”必须满足两个核心条件： 面积条件 ：所有小矩形的面积之和，必须等于最终形成的完美矩形的面积。 顶点条件 ：完美矩形的四个 外角 顶点（即最左下、最左上、最右下、最右上的顶点），在整个平面中只出现一次，并且 只能出现在这些小矩形集合的四个外角上 。而内部的其他顶点，必然出现2次或4次（因为小矩形拼接时，每个内部点都是2个或4个小矩形的公共角点）。 为什么是2次或4次？ 想象一个“T”型连接点，它会是3个矩形的交点，但实际上在二维网格中，一个点如果是矩形的角点，它要么是2个矩形的公共角点（在一条边上连接），要么是4个矩形的公共角点（像一个“十”字交叉的中心）。在完美矩形的内部，不可能出现只出现1次或3次的顶点。如果出现3次，说明有矩形重叠（多出一个角点）或存在空隙（某个角落缺失一个角点）。 更精确的理论依据是：在一个由轴对齐矩形完美拼接形成的大矩形中，除了四个外角顶点只出现1次，其余顶点（即所有内部顶点和边界上非角的顶点）出现的次数 必须为偶数 ，具体是2次或4次。 第二步：解题思路 找出最终完美矩形的边界 ： 遍历所有矩形，记录最终大矩形应有的左下角 (min_x, min_y) 和右上角 (max_x, max_y) 。这可以通过比较所有小矩形的 xi , yi (左下角) 和 ai , bi (右上角) 来得到。 计算大矩形的面积： (max_x - min_x) * (max_y - min_y) 。 面积条件验证 ： 遍历所有小矩形，计算每个小矩形的面积并累加。 比较累加面积是否等于大矩形的面积。如果不相等，直接返回 false 。因为如果有重叠，小矩形总面积会大于大矩形面积；如果有空隙，则会小于。 顶点条件验证 ： 我们需要一个数据结构来记录每个顶点出现的次数。这里使用哈希表（在Python中可以用 set 或 dict ，在Java/C++中用 HashSet 或 HashMap ）。 核心思想是：对于一个顶点，如果它已经存在于集合中，就移除它（表示成对出现）；如果不存在，就加入它。这样，最终集合中只会留下那些出现 奇数次的顶点 。 在一个完美矩形中，只有四个外角顶点应该出现奇数次（即1次），而所有内部顶点和边界非角顶点都会成对出现（即被加入后又被移除，最终不在集合中）。 所以，最终我们的集合应该 恰好包含4个点 ，并且它们就是步骤1中找到的大矩形的四个角点 (min_x, min_y) , (max_x, min_y) , (min_x, max_y) , (max_x, max_y) 。如果不是，就返回 false 。 第三步：详细步骤与示例 让我们用示例1来一步步走一遍。 输入 ： rectangles = [[1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4]] 找出大矩形边界 ： 所有 xi 和 yi 的最小值是 (1, 1) -> (min_x, min_y) 。 所有 ai 和 bi 的最大值是 (4, 4) -> (max_x, max_y) 。 大矩形面积 = (4-1) * (4-1) = 9。 计算小矩形总面积 ： 矩形1：(1,1,3,3) 面积 = (3-1)* (3-1)=4 矩形2：(3,1,4,2) 面积 = (4-3)* (2-1)=1 矩形3：(3,2,4,4) 面积 = (4-3)* (4-2)=2 矩形4：(1,3,2,4) 面积 = (2-1)* (4-3)=1 矩形5：(2,3,3,4) 面积 = (3-2)* (4-3)=1 总面积 = 4+1+2+1+1 = 9。✅ 面积条件满足。 顶点统计（使用集合） ： 初始化一个顶点集合 odd_vertices = set() 。 对每个矩形的四个顶点（左下、右下、左上、右上）进行处理： 顶点坐标： (xi, yi) , (ai, yi) , (xi, bi) , (ai, bi) 。 对每个顶点 v ： 如果 v 在 odd_vertices 中，就删除它（表示成对出现，抵消了）。 如果 v 不在，就加入它。 遍历过程： 矩形1：顶点 (1,1), (3,1), (1,3), (3,3) 加入集合 -> 集合: {(1,1),(3,1),(1,3),(3,3)} 矩形2：顶点 (3,1), (4,1), (3,2), (4,2) (3,1) 已在，删除 -> 集合: {(1,1),(1,3),(3,3)} (4,1) 加入 -> 集合: {(1,1),(1,3),(3,3),(4,1)} (3,2) 加入 -> 集合: {(1,1),(1,3),(3,3),(4,1),(3,2)} (4,2) 加入 -> 集合: {(1,1),(1,3),(3,3),(4,1),(3,2),(4,2)} 矩形3：顶点 (3,2), (4,2), (3,4), (4,4) (3,2) 已在，删除 -> 集合去掉(3,2) -> {(1,1),(1,3),(3,3),(4,1),(4,2)} (4,2) 已在，删除 -> 集合去掉(4,2) -> {(1,1),(1,3),(3,3),(4,1)} (3,4) 加入 -> 集合: {(1,1),(1,3),(3,3),(4,1),(3,4)} (4,4) 加入 -> 集合: {(1,1),(1,3),(3,3),(4,1),(3,4),(4,4)} 矩形4：顶点 (1,3), (2,3), (1,4), (2,4) (1,3) 已在，删除 -> 集合去掉(1,3) -> {(1,1),(3,3),(4,1),(3,4),(4,4)} (2,3) 加入 -> 集合: {(1,1),(3,3),(4,1),(3,4),(4,4),(2,3)} (1,4) 加入 -> 集合: {(1,1),(3,3),(4,1),(3,4),(4,4),(2,3),(1,4)} (2,4) 加入 -> 集合: {(1,1),(3,3),(4,1),(3,4),(4,4),(2,3),(1,4),(2,4)} 矩形5：顶点 (2,3), (3,3), (2,4), (3,4) (2,3) 已在，删除 -> 集合去掉(2,3) -> {(1,1),(3,3),(4,1),(3,4),(4,4),(1,4),(2,4)} (3,3) 已在，删除 -> 集合去掉(3,3) -> {(1,1),(4,1),(3,4),(4,4),(1,4),(2,4)} (2,4) 已在，删除 -> 集合去掉(2,4) -> {(1,1),(4,1),(3,4),(4,4),(1,4)} (3,4) 已在，删除 -> 集合去掉(3,4) -> {(1,1),(4,1),(4,4),(1,4)} 最终 odd_vertices = {(1,1), (4,1), (1,4), (4,4)} 。 这正是大矩形的四个外角顶点： (min_x, min_y) , (max_x, min_y) , (min_x, max_y) , (max_x, max_y) 。✅ 顶点条件满足。 综合判断 ：面积条件满足，且最终集合恰好是四个大矩形角点，返回 true 。 第四步：算法实现要点 遍历所有矩形时，一定要用整数精度 （题目给出的坐标是整数），计算面积时注意可能溢出（在某些语言中）。 顶点去重逻辑 ：可以用一个 HashSet 存储点，但点需要用一种唯一的方式表示，例如将坐标 (x, y) 编码成一个字符串 "x,y" 或一个64位整数 (long) x << 32 | y 。 面积条件 是必要条件但不是充分条件。即使总面积相等，也可能存在重叠或空隙（但顶点条件能检测出来）。所以两个条件都必须检查。 边界检查 ：如果最终集合中的点不是4个，或者四个点不是大矩形的四个角点，直接返回 false 。 第五步：复杂度分析 时间复杂度：O(N)，其中 N 是矩形的个数。我们需要遍历每个矩形一次，每个矩形处理4个顶点，所以是 O(4N) = O(N)。 空间复杂度：O(N)，在最坏情况下，哈希集合可能需要存储所有顶点（即 4N 个点），但通常由于顶点抵消，最终集合只会有少量点。 总结 ：这道题通过哈希表巧妙地统计顶点出现次数的奇偶性，结合面积验证，高效地判断了矩形是否完美拼接。关键在于理解“完美矩形”的顶点出现规律，并将其转化为集合的“成对抵消”操作。