LeetCode 391. 完美矩形

约 7 分钟
文章信息 8 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 腾讯 拼多多 小米
标签
数组 哈希表 数学 几何 扫描线

题目描述

✅ 391. 完美矩形

image-20260928223930645

image-20260928223930647

image-20260928223930648

题意分析

每个小矩形的边都平行于坐标轴，要求它们恰好拼成一个完整的大矩形：内部不能有空隙，也不能有重叠，共用边或角点是允许的。

若能完美覆盖，目标大矩形一定由所有小矩形的最小左、下边界和最大右、上边界确定。只比较面积还不够，因为重叠增加的面积可能与空隙减少的面积相抵消。

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

核心思路

[!blue]

同时检查面积和角点。遍历所有矩形，记录外框 minX、minY、maxX、maxY，并累加每个小矩形的面积。小矩形面积之和必须等于外框面积，重叠部分在这个和中会被重复计算。

对每个矩形的四个角点做一次集合切换：不存在就加入，已经存在就删除。处理结束后，集合中恰好保留出现奇数次的坐标。完美拼接时，四个外角各出现一次，其他拼接位置的角点出现次数都是偶数，因此最终必须只剩外框的四个具体角点。

这两个条件的充分性可以通过划分小格理解。用所有横纵边界把外框划成小格，每格内部的覆盖次数固定。取格内一点，统计横纵坐标都不超过该点的角点：包含该点的矩形只有左下角满足条件，不包含该点的矩形则贡献 0、2 或 4 个。因此这些角点总数的奇偶，恰好等于该格覆盖次数的奇偶。

当剩余奇数角点只有外框四角时，内部每个小格的覆盖次数都和完整外框一样为奇数，也就至少被覆盖一次，排除了空隙。此时总面积又恰好等于外框面积，任何小格都不能被多覆盖，否则面积和必然超出。所以所有小格只能恰好覆盖一次，重叠也被排除。划分小格只用于说明正确性，代码无需建立网格。

面积使用宽整数，先转换坐标再相减、相乘。角点键需要完整区分横纵坐标：Java 用带分隔符的字符串，Go 直接用长度为 2 的数组作为键。

解题步骤

  1. 初始化外框边界、面积和及空的角点集合。
  2. 遍历每个矩形，更新四条外框边界，累加宽乘高，并对四个角点分别切换集合成员。
  3. 计算外框面积。若面积和不同，或集合中不是恰好 4 个点，返回 false。
  4. 检查剩下的四个点是否分别为外框的左下、左上、右下、右上角；全部满足才返回 true。

代码实现

class Solution {
    // 所有小矩形的面积和必须等于外包大矩形面积，面积使用宽整数，并在相减之前转换坐标。
    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) * ((long) y2 - y1);
            toggle(corners, x1, y1);
            toggle(corners, x1, y2);
            toggle(corners, x2, y1);
            toggle(corners, x2, y2);
        }

        long coverArea = ((long) maxX - minX) * ((long) 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 {
    // 所有小矩形的面积和必须等于外包大矩形面积，面积使用宽整数，并在相减之前转换坐标。
    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) - int64(x1)) * (int64(y2) - int64(y1))
        toggle(x1, y1)
        toggle(x1, y2)
        toggle(x2, y1)
        toggle(x2, y2)
    }

    coverArea := (int64(maxX) - int64(minX)) * (int64(maxY) - int64(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)$，最坏保存线性数量角点。

关键点总结

[!green]

  • 面积统计每一层覆盖，角点集合只统计覆盖结构的奇偶，两种信息共同排除空隙和重叠。
  • 切换集合等价于记录出现次数的奇偶，不需要保存完整计数。
  • 验证的是外框四个具体坐标，不能只判断剩余点数为 4。

易错点总结

[!yellow]

  • 只比较面积无法排除空隙与重叠相抵；只检查角点奇偶也无法排除奇数层重复覆盖。
  • 坐标范围允许面积超过 int，应先把坐标转成 long 或 int64 再相减、相乘，不能等窄整数运算完成后才转换。
  • 字符串键中的横纵坐标必须有分隔符，否则不同坐标可能拼成相同文本。
  • 每个矩形的四角都必须参与切换，不能把共享角点只处理一次。

相似题目

题目 难度 关联与区别
223. 矩形面积 中等 面积计算是基础，但总面积相等还不足以独自排除重叠与空洞，本题需额外验证边界结构。
850. 矩形面积 II 困难 同样处理多个轴对齐矩形，原题计算并集面积，本题判断它们是否无重叠无空隙地覆盖一个矩形。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/73047705
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！