Hard

题目描述

给定一个数组 rectangles，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个轴对齐的矩形。矩形的左下角点为 (xi, yi)，右上角点为 (ai, bi)。

如果所有矩形一起恰好覆盖了某个矩形区域，返回 true。

示例 1：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。

示例 2：

输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相互重叠的矩形。

提示：

  • 1 <= rectangles.length <= 2 * 10^4
  • rectangles[i].length == 4
  • -10^5 <= xi < ai <= 10^5
  • -10^5 <= yi < bi <= 10^5

解题思路

这是一个几何问题，需要判断给定的矩形是否能完美拼接成一个大矩形。

核心思路：

完美矩形需要满足两个条件：

  1. 面积匹配：所有小矩形的面积之和等于最终大矩形的面积
  2. 顶点唯一性：除了大矩形的四个顶点外，其他所有顶点都应该出现偶数次

算法步骤：

  1. 遍历所有矩形，计算总面积和边界范围
  2. 使用哈希集合记录所有顶点，如果顶点重复出现则移除（利用异或性质）
  3. 最终集合中应该只剩下4个顶点，且这4个顶点恰好是大矩形的四个角

关键观察：

  • 在完美拼接中，内部顶点会被相邻矩形共享，出现偶数次
  • 只有最外层的4个角点会出现奇数次（实际上是1次）
  • 使用集合的添加/删除操作可以自动过滤出现偶数次的点

这种方法的时间复杂度为O(n)，空间复杂度也是O(n)，是最优解法。

代码实现

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        long long area = 0;
        int minX = INT_MAX, minY = INT_MAX;
        int maxX = INT_MIN, maxY = INT_MIN;
        
        set<pair<int, int>> points;
        
        for (auto& rect : rectangles) {
            int x1 = rect[0], y1 = rect[1];
            int x2 = rect[2], y2 = rect[3];
            
            area += (long long)(x2 - x1) * (y2 - y1);
            
            minX = min(minX, x1);
            minY = min(minY, y1);
            maxX = max(maxX, x2);
            maxY = max(maxY, y2);
            
            vector<pair<int, int>> corners = {{x1, y1}, {x1, y2}, {x2, y1}, {x2, y2}};
            for (auto& corner : corners) {
                if (points.count(corner)) {
                    points.erase(corner);
                } else {
                    points.insert(corner);
                }
            }
        }
        
        return area == (long long)(maxX - minX) * (maxY - minY) &&
               points.size() == 4 &&
               points.count({minX, minY}) &&
               points.count({minX, maxY}) &&
               points.count({maxX, minY}) &&
               points.count({maxX, maxY});
    }
};

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        area = 0
        minX = minY = float('inf')
        maxX = maxY = float('-inf')
        
        points = set()
        
        for x1, y1, x2, y2 in rectangles:
            area += (x2 - x1) * (y2 - y1)
            
            minX = min(minX, x1)
            minY = min(minY, y1)
            maxX = max(maxX, x2)
            maxY = max(maxY, y2)
            
            corners = [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]
            for corner in corners:
                if corner in points:
                    points.remove(corner)
                else:
                    points.add(corner)
        
        return (area == (maxX - minX) * (maxY - minY) and
                len(points) == 4 and
                {(minX, minY), (minX, maxY), (maxX, minY), (maxX, maxY)} == points)

public class Solution {
    public bool IsRectangleCover(int[][] rectangles) {
        long area = 0;
        int minX = int.MaxValue, minY = int.MaxValue;
        int maxX = int.MinValue, maxY = int.MinValue;
        
        var points = new HashSet<(int, int)>();
        
        foreach (var rect in rectangles) {
            int x1 = rect[0], y1 = rect[1];
            int x2 = rect[2], y2 = rect[3];
            
            area += (long)(x2 - x1) * (y2 - y1);
            
            minX = Math.Min(minX, x1);
            minY = Math.Min(minY, y1);
            maxX = Math.Max(maxX, x2);
            maxY = Math.Max(maxY, y2);
            
            var corners = new (int, int)[] {(x1, y1), (x1, y2), (x2, y1), (x2, y2)};
            foreach (var corner in corners) {
                if (points.Contains(corner)) {
                    points.Remove(corner);
                } else {
                    points.Add(corner);
                }
            }
        }
        
        return area == (long)(maxX - minX) * (maxY - minY) &&
               points.Count == 4 &&
               points.Contains((minX, minY)) &&
               points.Contains((minX, maxY)) &&
               points.Contains((maxX, minY)) &&
               points.Contains((maxX, maxY));
    }
}

var isRectangleCover = function(rectangles) {
    if (rectangles.length === 0) return false;
    
    let minX = Infinity, minY = Infinity;
    let maxX = -Infinity, maxY = -Infinity;
    let totalArea = 0;
    let corners = new Set();
    
    for (let [x1, y1, x2, y2] of rectangles) {
        minX = Math.min(minX, x1);
        minY = Math.min(minY, y1);
        maxX = Math.max(maxX, x2);
        maxY = Math.max(maxY, y2);
        
        totalArea += (x2 - x1) * (y2 - y1);
        
        let rectCorners = [
            x1 + ',' + y1,
            x1 + ',' + y2,
            x2 + ',' + y1,
            x2 + ',' + y2
        ];
        
        for (let corner of rectCorners) {
            if (corners.has(corner)) {
                corners.delete(corner);
            } else {
                corners.add(corner);
            }
        }
    }
    
    let expectedArea = (maxX - minX) * (maxY - minY);
    if (totalArea !== expectedArea) return false;
    
    if (corners.size !== 4) return false;
    
    let expectedCorners = new Set([
        minX + ',' + minY,
        minX + ',' + maxY,
        maxX + ',' + minY,
        maxX + ',' + maxY
    ]);
    
    for (let corner of corners) {
        if (!expectedCorners.has(corner)) return false;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是矩形的数量。需要遍历所有矩形，每个矩形处理4个顶点
空间复杂度O(n)，最坏情况下集合中可能存储 4n 个顶点