设计完美矩形

题目描述

给你一个数组 rectangles，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个矩形的左下角点 (xi, yi) 和右上角点 (ai, bi) 的坐标。所有矩形都放置在二维平面中，且 边与坐标轴平行。需要判断这些矩形是否 精确覆盖 了一个完整的矩形区域，也就是说：

1. 没有重叠：任意两个矩形之间没有重叠部分（允许边或角接触）。
2. 没有空隙：所有矩形组合起来刚好铺满一个矩形区域，没有任何空缺。
3. 完全覆盖：不能有任何矩形超出这个完整矩形区域的范围。

如果满足所有条件，返回 true；否则返回 false。

解题思路分析

这个问题可以通过 几何面积累加 和 顶点出现次数统计 结合哈希表来解决。核心思路如下：

1. 面积相等条件
   将所有小矩形的面积加起来，记为 sumArea。
   同时，通过小矩形计算出整个完美矩形的 左下角 和 右上角 坐标，进而计算出这个完美矩形的面积 fullArea。
   如果 sumArea != fullArea，一定不是完美矩形（有空缺或重叠）。

2. 顶点匹配条件
   对于完美矩形来说，除了最外层的四个角点，内部顶点出现的次数一定是偶数次（因为每个内点都是两个或四个矩形的交界点）。
   具体来说：

   • 每个小矩形的四个顶点都会在整体中出现。
   • 最终完美矩形应该有且仅有 四个顶点出现奇数次，其余顶点出现偶数次。
   • 这四个奇数次顶点，就是整个完美矩形的四个角点。

所以我们可以：

• 用哈希表记录每个顶点出现的次数。
• 遍历每个小矩形，增加其四个顶点的出现次数。
• 最后检查哈希表中出现奇数次的顶点是否正好是四个，并且它们构成的矩形面积等于前面计算的 fullArea（避免面积相等但形状不对的情况）。

逐步详细讲解

步骤 1：初始化变量

• sumArea：累加所有小矩形的面积。
• minX, minY, maxX, maxY：记录最终完美矩形的最小左下角和最大右上角。
• countMap：哈希表，键为顶点坐标 (x, y)，值为出现次数。

步骤 2：遍历每个矩形

对于 rectangles 中的每个矩形 [x, y, a, b]：

1. 计算面积 (a - x) * (b - y)，累加到 sumArea。
2. 更新 minX = min(minX, x)，minY = min(minY, y)，maxX = max(maxX, a)，maxY = max(maxY, b)。
3. 四个顶点分别是：
   • (x, y)
   • (x, b)
   • (a, y)
   • (a, b)
4. 对于每个顶点，在 countMap 中计数：
   • 如果 countMap[(x, y)] 不存在，则设为 1。
   • 如果存在，则加 1（或更简单：用异或操作，偶数次出现会抵消，后面会说明）。

步骤 3：计算完整矩形面积

• fullArea = (maxX - minX) * (maxY - minY)
• 如果 sumArea != fullArea，直接返回 false。

步骤 4：检查顶点出现次数

我们需要四个角点出现奇数次，其余点出现偶数次。

更巧妙的做法是：

• 用集合（或哈希表）记录每个顶点出现的 奇偶性（出现奇数次保留，出现偶数次删除）。
• 这样最后集合里应该恰好剩下四个顶点，并且就是 (minX, minY), (minX, maxY), (maxX, minY), (maxX, maxY)。

具体操作：

对每个矩形的四个顶点 (x, y)：
   如果集合中有 (x, y)，则删除（偶数次抵消）；
   否则加入集合（奇数次保留）。

遍历完所有矩形后，集合中应该恰好有四个顶点，且这四个顶点是完整矩形的四个角点。

步骤 5：最终判断

1. 检查集合大小是否为 4。
2. 检查集合中是否包含且仅包含 (minX, minY), (minX, maxY), (maxX, minY), (maxX, maxY)。

如果都满足，返回 true，否则 false。

为什么这样是正确的？

• 面积相等 确保了没有重叠或空隙的整体面积正确。
• 顶点奇偶性 确保了每个内点都是偶数次出现（被抵消），只有四个外角点是奇数次。
• 如果矩形有重叠，则重叠区域的顶点会出现奇数次（不是完整矩形的角点），导致集合大小不等于 4。
• 如果矩形有空缺，则面积 sumArea 会小于 fullArea，第一步就会被检测出来。

示例演示

例 1：

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

1. 计算总面积 = 4 + 2 + 2 + 1 + 1 = 10。
2. 整体矩形：左下角 (1,1)，右上角 (4,4)，面积 = 9。
   面积不相等 → 返回 false（实际上这里面积是 9，但总面积是 10，说明有重叠）。

例 2：

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,3,3,4]
]

1. 总面积 = 4 + 2 + 1 + 1 = 8。
2. 整体矩形：左下角 (1,1)，右上角 (4,4)，面积 = 9。
   面积不相等 → false（有空隙）。

例 3（正确情况）：

rectangles = [
  [1,1,3,3],
  [3,1,4,3],
  [3,3,4,4],
  [1,3,3,4]
]

1. 总面积 = 4 + 2 + 1 + 2 = 9。
2. 整体矩形：左下角 (1,1)，右上角 (4,4)，面积 = 9。
3. 顶点集合：
   • 遍历后集合中应该剩下：(1,1), (1,4), (4,1), (4,4)。
   • 且这四个点就是整体矩形的四个角点。
     → 返回 true。

时间复杂度与空间复杂度

• 时间复杂度：O(n)，n 为矩形个数。
• 空间复杂度：O(n)，用于存储顶点集合（最多 4n 个顶点，但集合最多保留 4 个）。

总结

这道题的关键在于：

1. 面积相等 是必要条件。
2. 顶点奇偶性 通过集合的添加/删除操作巧妙统计。
3. 最后检查集合中是否正好是四个预期角点。

这种方法避免了复杂的重叠判断和空隙扫描，只用哈希表就能高效解决。