LeetCode 391. 完美矩形

2024-05-24 HGNULB 约 11 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 391. 完美矩形

题意分析

给一组轴对齐的矩形，每个用左下角和右上角坐标描述。要判断它们是否恰好拼成一个大矩形：既不能有任何重叠，也不能留下任何空隙，整体轮廓必须是一个矩形。

这里有三个独立的失败方式，缺一不可地都要检出：区域有洞、区域有重叠、外轮廓不是矩形（比如拼成了 L 形）。任何只检查其中一两项的方案都能被构造出反例。

坐标是 32 位整数，矩形数量可达两万。单个矩形的面积就可能超过 32 位，面积求和更是必须用 64 位。

「轴对齐」是重要的简化条件：所有边要么水平要么垂直，因此每个矩形只有四个角点，且角点坐标都是整数，可以直接当作哈希键。

边界情况：只有一个矩形时天然成立；输入为空时按题目约束不会出现，但实现上应当有明确行为。

解法：面积校验 + 角点抵消

核心思路

最朴素的想法是把平面离散化后逐格统计覆盖次数，要求每格恰好被覆盖一次。逻辑上无懈可击，但坐标跨度可达十亿，离散化后的网格规模是矩形数量的平方级，两万个矩形完全承受不起。

换个角度，用两个互相独立的必要条件去卡：

第一个是面积守恒。先求出所有矩形的外包矩形（横纵坐标各取极值），若拼接完美，则所有小矩形的面积之和必须恰好等于外包矩形的面积。有洞会让和偏小，有重叠会让和偏大。但它单独不够——重叠面积和空洞面积恰好相等时就会漏判。

第二个是角点奇偶。考察一个理想的完美覆盖：任取一个不在外轮廓上的点，它要么落在某条边的内部（被两个矩形共享，作为角点出现 2 次），要么落在四块交汇处（作为角点出现 4 次），要么根本不是任何矩形的角点。总之内部的角点出现次数必为偶数。而外包矩形的四个角，各自只属于唯一一个小矩形，出现次数为 1，是奇数。

于是用一个集合做「出现即删、不存在即加」的开关操作，遍历完所有矩形后，集合里剩下的正是所有出现奇数次的点。维持的不变量是：集合最终必须恰好含有外包矩形的四个角，不多不少。这一条同时排除了 L 形轮廓（会多出凹角）和角点错位的重叠情形。

两个条件合在一起就是充要的：面积守恒保证了「覆盖总量」正确，角点奇偶保证了「拼接结构」正确，任一单独成立而另一个不成立的情形都会被另一条抓住。

解题步骤

用第一个矩形初始化外包边界的四个极值，并准备一个空的角点集合和 64 位的面积累加器。用第一个矩形而不是用整型极值初始化，可以避免哨兵与真实坐标混淆。

遍历每个矩形，先用它的左下角更新最小横纵坐标、右上角更新最大横纵坐标。所有矩形扫完后，这四个值就界定了外包矩形。

累加面积时先把边长差转成 64 位再相乘。单个矩形的宽高各自可达十亿量级，在 32 位下相乘必然溢出。

对当前矩形的四个角点各做一次开关操作：集合里已有就删掉，没有就加入。这等价于对每个点的出现次数取模 2，只保留奇偶性。

遍历结束后先算外包矩形面积并与累加值比较，不等直接返回假。这一步能以极低成本筛掉大量输入。

再检查集合大小是否恰好为 4，然后逐个确认这四个点就是外包矩形的四个角。只查大小不查具体坐标是不够的——完全可能剩下四个位置错误的点。

以 rectangles = [[1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4]] 走一遍：初始边界取自第一个矩形，即最小点 $(1, 1)$、最大点 $(3, 3)$，面积为 0，集合为空。

处理 [1,1,3,3]：边界不变。面积加 $2 \times 2 = 4$，累计 4。四个角 $(1,1)$、$(1,3)$、$(3,1)$、$(3,3)$ 都不在集合中，全部加入。

处理 [3,1,4,2]：最大横坐标更新为 4。面积加 $1 \times 1 = 1$，累计 5。角点中 $(3,1)$ 已在集合里被删除，$(3,2)$、$(4,1)$、$(4,2)$ 加入。集合现为 ${(1,1), (1,3), (3,3), (3,2), (4,1), (4,2)}$。

处理 [3,2,4,4]：最大纵坐标更新为 4。面积加 $1 \times 2 = 2$，累计 7。$(3,2)$ 被删除，$(3,4)$ 加入，$(4,2)$ 被删除，$(4,4)$ 加入。集合现为 ${(1,1), (1,3), (3,3), (4,1), (3,4), (4,4)}$。

处理 [1,3,2,4]：边界不变。面积加 1，累计 8。$(1,3)$ 被删除，$(1,4)$、$(2,3)$、$(2,4)$ 加入。集合现为 ${(1,1), (3,3), (4,1), (3,4), (4,4), (1,4), (2,3), (2,4)}$。

处理 [2,3,3,4]：边界不变。面积加 1，累计 9。四个角 $(2,3)$、$(2,4)$、$(3,3)$、$(3,4)$ 全部已在集合中，因此全部被删除。集合最终为 ${(1,1), (4,1), (1,4), (4,4)}$。

校验：外包矩形是 $(1,1)$ 到 $(4,4)$，面积 $3 \times 3 = 9$，与累计的 9 相等。集合大小为 4，且四个点恰好是外包矩形的四角。返回真。

再看一个只有面积检查会漏判的反例 [[0,0,2,1], [1,0,3,1], [0,1,2,2]]：三块面积分别是 2、2、2，合计 6；外包矩形是 $(0,0)$ 到 $(3,2)$，面积同样是 6，面积检查完全通过。但实际上区域 $(1,0)$–$(2,1)$ 被覆盖了两次，而 $(2,1)$–$(3,2)$ 是个空洞，两者面积恰好抵消。此时角点集合里会剩下 $(0,0)$、$(1,0)$、$(1,1)$、$(2,0)$、$(3,0)$、$(3,1)$、$(0,2)$、$(2,2)$ 共八个点，大小不等于 4，被角点检查正确判假。这个例子说明两项检查缺一不可。

代码实现

class Solution {
    // 所有小矩形的面积和必须等于外包大矩形面积，面积计算要用 long 避免溢出。
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles.length == 0) {
            return false;
        }

        long area = 0;
        int minX = rectangles[0][0];
        int minY = rectangles[0][1];
        int maxX = rectangles[0][2];
        int maxY = rectangles[0][3];

        Set<String> corners = new HashSet<>();

        for (int[] rectangle : rectangles) {
            int x1 = rectangle[0];
            int y1 = rectangle[1];
            int x2 = rectangle[2];
            int y2 = rectangle[3];

            minX = Math.min(minX, x1);
            minY = Math.min(minY, y1);
            maxX = Math.max(maxX, x2);
            maxY = Math.max(maxY, y2);

            area += (long) (x2 - x1) * (y2 - y1);
            toggle(corners, x1, y1);
            toggle(corners, x1, y2);
            toggle(corners, x2, y1);
            toggle(corners, x2, y2);
        }

        long coverArea = (long) (maxX - minX) * (maxY - minY);
        if (area != coverArea || corners.size() != 4) {
            return false;
        }

        return corners.contains(key(minX, minY))
                && corners.contains(key(minX, maxY))
                && corners.contains(key(maxX, minY))
                && corners.contains(key(maxX, maxY));
    }

    private void toggle(Set<String> corners, int x, int y) {
        String k = key(x, y);
        if (corners.contains(k)) {
            corners.remove(k);
            return;
        }

        corners.add(k);
    }

    private String key(int x, int y) {
        return x + "," + y;
    }
}

func isRectangleCover(rectangles [][]int) bool {
    // 所有小矩形的面积和必须等于外包大矩形面积，面积计算要用 long 避免溢出。
    if len(rectangles) == 0 {
        return false
    }

    minX, minY := rectangles[0][0], rectangles[0][1]
    maxX, maxY := rectangles[0][2], rectangles[0][3]
    area := int64(0)
    corners := make(map[[2]int]bool)

    toggle := func(x, y int) {
        point := [2]int{x, y}
        if corners[point] {
            delete(corners, point)
            return
        }

        corners[point] = true
    }

    for _, r := range rectangles {
        x1, y1 := r[0], r[1]
        x2, y2 := r[2], r[3]

        if x1 < minX {
            minX = x1
        }
        if y1 < minY {
            minY = y1
        }
        if x2 > maxX {
            maxX = x2
        }
        if y2 > maxY {
            maxY = y2
        }

        area += int64(x2-x1) * int64(y2-y1)
        toggle(x1, y1)
        toggle(x1, y2)
        toggle(x2, y1)
        toggle(x2, y2)
    }

    coverArea := int64(maxX-minX) * int64(maxY-minY)
    if area != coverArea || len(corners) != 4 {
        return false
    }

    if !corners[[2]int{minX, minY}] || !corners[[2]int{minX, maxY}] {
        return false
    }

    if !corners[[2]int{maxX, minY}] || !corners[[2]int{maxX, maxY}] {
        return false
    }

    return true
}

复杂度分析

时间复杂度：$O(n)$，只遍历矩形数组一次，每个矩形做常数次极值更新、一次乘法和四次哈希开关操作，最后的校验也是常数次查询。

空间复杂度：$O(n)$，集合中同时存在的点数不超过角点总数 $4n$；实际由于内部角点不断被抵消，规模通常远小于这个上界。

关键点总结

判定「完美拼接」不必真的构造覆盖。用若干条容易计算的必要条件，且让它们合起来成为充分条件，是几何判定题的标准套路。

面积守恒管「总量」，角点奇偶管「结构」，两者正交。只用一条都能被构造反例，理解这一点比记住结论更重要。

出现次数只关心奇偶时，用集合的「有则删、无则加」代替计数哈希表，省一半空间且代码更短，这个技巧在异或去重类问题里同样通用。

角点检查必须同时验证「个数为 4」和「就是外包矩形的四个角」。只查个数会放过角点错位的构造。

坐标接近 32 位上限时，任何乘法之前都要先扩宽类型。这类溢出在本地小样例上完全看不出来。

面试视角：先说清三种失败方式，再逐条给出对应的检查，最后论证两条检查合起来为何充分。若面试官追问，可以补充「离散化后逐格计数」的暴力解法及其复杂度，说明为什么放弃它；也可以提到还有一种按扫描线维护区间的解法，但代码量远大于本方案。

易错点总结

错误写法：只检查面积守恒。[[0,0,2,1], [1,0,3,1], [0,1,2,2]] → 面积和与外包面积都是 6，会返回真，但实际存在一处重叠和一处等面积的空洞，正确答案是假。

错误写法：只检查角点奇偶而不检查面积。构造出两块不相交却角点恰好抵消的输入时会漏判，两项检查必须同时保留。

错误写法：面积累加用 32 位整数。坐标接近十亿的单个大矩形 → 宽高相乘直接溢出成负数，与外包面积的比较失去意义。

错误写法：角点检查只验证集合大小为 4。存在四个位置错误的奇数次角点的构造 → 会返回真，必须逐个比对是否为外包矩形的四角。

错误写法：用「加入并计数」的哈希表统计出现次数，最后判断是否都为偶数。这不仅多占空间，还容易忘记外包四角本就该是奇数，从而把正确输入判假。

错误写法：外包边界用整型最大值和最小值初始化，却写反了方向（最小值变量初始化为最小值）。任意输入 → 边界永远不会被更新，外包面积算成极大值，一律返回假。

错误写法：用字符串拼接坐标作键时不加分隔符。点 $(1, 23)$ 与 $(12, 3)$ → 拼出同一个键 "123"，两个不同的点被错误抵消。

错误写法：把角点坐标压缩成单个整数时移位位数不足。坐标可达十亿，需要 31 位以上 → 压缩后高低位互相污染，不同点冲撞成同一键。

错误写法：更新外包边界时用了错误的坐标分量，比如用右上角去更新最小值。任意多矩形输入 → 外包矩形算小了，面积校验必然失败。

错误写法：认为矩形一定按某种顺序给出，于是只用第一个和最后一个矩形推算外包边界。乱序输入 → 边界不完整，面积比较随机地通过或失败。

相似题目

题目	难度	考察点
836. 矩形重叠	简单	两个矩形是否相交，考察区间投影与边界等号的取舍
223. 矩形面积	中等	容斥求并集面积，重叠部分要精确算出而非只判断有无
850. 矩形面积 II	困难	多矩形并集面积，需要扫描线配合坐标离散化
218. 天际线问题	困难	扫描线加堆维护当前最大高度，输出轮廓拐点
1401. 圆和矩形是否有重叠	中等	非轴对齐图形的相交判定，靠最近点距离而非角点枚举