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]。

自建示例

三个矩形无缝拼接:

输入:rectangles = [[0,0,1,2],[1,0,3,1],[1,1,3,2]]
输出:true
解释:三个区域没有重叠或空洞,恰好覆盖左下角 (0,0)、右上角 (3,2) 的大矩形。

内部发生重叠:

输入:rectangles = [[0,0,2,2],[1,0,3,2]]
输出:false
解释:两个矩形在横坐标 1 到 2 的区域内重叠,不能视为精确覆盖。

面积检查内部,角点奇偶检查边界

先求所有小矩形的总面积和外接边界 [minX,maxX] × [minY,maxY]。若存在重叠,面积会多算;若存在空洞,面积会少算,因此总面积必须等于外接矩形面积。

面积相等还不足以排除某些内部重叠与空洞组合,所以对每个小矩形的四个角做奇偶切换:内部共享角会出现偶数次而被抵消,最终集合只能留下外接矩形的四个角。两个条件同时满足时,边界拼接没有重叠或空缺。

C++ 实现

class Solution {
public:
    bool isRectangleCover(
        std::vector<std::vector<int>>& rectangles) {
        long long area = 0;
        int minX = INT_MAX;
        int minY = INT_MAX;
        int maxX = INT_MIN;
        int maxY = INT_MIN;
        std::set<std::pair<int, int>> corners;

        auto toggle = [&](int x, int y) {
            std::pair<int, int> 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)。