0391. Perfect Rectangle
=======================
题目信息
--------
:题号: 0391
:难度: Hard
:主题: 轴对齐矩形、精确覆盖、重叠、空洞
:原题: `LeetCode 0391 `_
:重点: 所有小矩形面积必须恰好组成一个外接矩形、内部不能重叠或留空、共享边界允许
题目重述
--------
给定若干轴对齐矩形,``rectangles[i] = [xi, yi, ai, bi]`` 表示左下角为 ``(xi, yi)``、右上角为 ``(ai, bi)`` 的矩形,其中 ``xi < ai`` 且 ``yi < bi``。判断这些小矩形的并集是否恰好等于某一个完整的大矩形。
合法覆盖中,小矩形可以共享边或角,但内部面积不能重叠,大矩形内部也不能存在未覆盖空洞;外轮廓必须只有目标大矩形的四条边。矩形数量位于 ``[1, 2 * 10^4]``,所有坐标位于 ``[-10^5, 10^5]``。
自建示例
--------
三个矩形无缝拼接:
.. code-block:: text
输入:rectangles = [[0,0,1,2],[1,0,3,1],[1,1,3,2]]
输出:true
解释:三个区域没有重叠或空洞,恰好覆盖左下角 (0,0)、右上角 (3,2) 的大矩形。
内部发生重叠:
.. code-block:: text
输入:rectangles = [[0,0,2,2],[1,0,3,2]]
输出:false
解释:两个矩形在横坐标 1 到 2 的区域内重叠,不能视为精确覆盖。
面积检查内部,角点奇偶检查边界
--------------------------------
先求所有小矩形的总面积和外接边界 ``[minX,maxX] × [minY,maxY]``。若存在重叠,面积会多算;若存在空洞,面积会少算,因此总面积必须等于外接矩形面积。
面积相等还不足以排除某些内部重叠与空洞组合,所以对每个小矩形的四个角做奇偶切换:内部共享角会出现偶数次而被抵消,最终集合只能留下外接矩形的四个角。两个条件同时满足时,边界拼接没有重叠或空缺。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
bool isRectangleCover(
std::vector>& rectangles) {
long long area = 0;
int minX = INT_MAX;
int minY = INT_MAX;
int maxX = INT_MIN;
int maxY = INT_MIN;
std::set> corners;
auto toggle = [&](int x, int y) {
std::pair point = {x, y};
auto it = corners.find(point);
if (it == corners.end()) {
corners.insert(point);
} else {
corners.erase(it);
}
};
for (const auto& rectangle : rectangles) {
int x1 = rectangle[0];
int y1 = rectangle[1];
int x2 = rectangle[2];
int y2 = rectangle[3];
minX = std::min(minX, x1);
minY = std::min(minY, y1);
maxX = std::max(maxX, x2);
maxY = std::max(maxY, y2);
area += 1LL * (x2 - x1) * (y2 - y1);
toggle(x1, y1);
toggle(x1, y2);
toggle(x2, y1);
toggle(x2, y2);
}
long long boundingArea =
1LL * (maxX - minX) * (maxY - minY);
if (area != boundingArea || corners.size() != 4) {
return false;
}
return corners.count({minX, minY})
&& corners.count({minX, maxY})
&& corners.count({maxX, minY})
&& corners.count({maxX, maxY});
}
};
代码分析
--------
角点集合只保留出现奇数次的坐标,内部共享角和边界分割点会抵消,四个外轮廓角必须最终存在。面积使用 ``long long``,避免坐标差乘积超出 32 位。每个矩形进行常数次有序集合操作,时间复杂度为 ``O(m log m)``,额外空间为 ``O(m)``。