Hard

题目描述

给你一个轴对齐矩形数组 rectangles。对于 rectangle[i] = [xi1, yi1, xi2, yi2]，其中 (xi1, yi1) 是第 i 个矩形的左下角坐标，(xi2, yi2) 是第 i 个矩形的右上角坐标。

计算平面中所有矩形覆盖的总面积。任何被两个或多个矩形覆盖的区域只计算一次。

返回总面积。由于答案可能太大，请返回 10^9 + 7 的模。

示例 1：

输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出：6
解释：如图所示，总共有 6 个单位的面积被覆盖。从 (1,1) 到 (2,2)，绿色矩形和红色矩形重叠。从 (1,0) 到 (2,3)，三个矩形都重叠。

示例 2：

输入：rectangles = [[0,0,1000000000,1000000000]]
输出：49
解释：答案是 10^18 对 (10^9 + 7) 取模的结果，即 49。

提示：

  • 1 <= rectangles.length <= 200
  • rectanges[i].length == 4
  • 0 <= xi1, yi1, xi2, yi2 <= 10^9
  • xi1 <= xi2
  • yi1 <= yi2
  • 所有矩形都有非零面积

解题思路

这是一个经典的扫描线算法问题，需要计算多个矩形的并集面积。

主要思路：

  1. 坐标离散化：由于坐标范围很大（10^9），但矩形数量有限（≤200），我们只需要关心矩形的边界坐标。提取所有x坐标和y坐标并排序去重。

  2. 网格分割：离散化后的坐标将平面分割成若干个小矩形网格。我们遍历每个网格，判断它是否被任何矩形覆盖。

  3. 覆盖判断：对于网格 (x1,y1) 到 (x2,y2)，检查是否存在矩形完全包含这个网格。

  4. 面积累加：将所有被覆盖的网格面积累加，注意取模运算。

算法步骤：

  • 提取所有不重复的x坐标和y坐标并排序
  • 双重循环遍历所有可能的网格
  • 对每个网格，检查是否被任一矩形覆盖
  • 累加被覆盖网格的面积

时间复杂度分析：

  • 坐标离散化：O(n log n)
  • 网格遍历：O(n²)，其中n是矩形数量
  • 覆盖检查：每个网格需要O(n)时间检查所有矩形
  • 总体：O(n³)

这种方法简单直观，对于题目给定的数据规模（n≤200）完全可行。

代码实现

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        const int MOD = 1e9 + 7;
        
        // 提取所有x坐标和y坐标
        set<int> xSet, ySet;
        for (auto& rect : rectangles) {
            xSet.insert(rect[0]);
            xSet.insert(rect[2]);
            ySet.insert(rect[1]);
            ySet.insert(rect[3]);
        }
        
        vector<int> xs(xSet.begin(), xSet.end());
        vector<int> ys(ySet.begin(), ySet.end());
        
        long long area = 0;
        
        // 遍历每个可能的网格
        for (int i = 0; i < xs.size() - 1; i++) {
            for (int j = 0; j < ys.size() - 1; j++) {
                int x1 = xs[i], x2 = xs[i + 1];
                int y1 = ys[j], y2 = ys[j + 1];
                
                // 检查这个网格是否被任何矩形覆盖
                for (auto& rect : rectangles) {
                    if (rect[0] <= x1 && x2 <= rect[2] && 
                        rect[1] <= y1 && y2 <= rect[3]) {
                        area = (area + (long long)(x2 - x1) * (y2 - y1)) % MOD;
                        break;
                    }
                }
            }
        }
        
        return area;
    }
};

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # 提取所有x坐标和y坐标
        xs = sorted(set(x for rect in rectangles for x in [rect[0], rect[2]]))
        ys = sorted(set(y for rect in rectangles for y in [rect[1], rect[3]]))
        
        area = 0
        
        # 遍历每个可能的网格
        for i in range(len(xs) - 1):
            for j in range(len(ys) - 1):
                x1, x2 = xs[i], xs[i + 1]
                y1, y2 = ys[j], ys[j + 1]
                
                # 检查这个网格是否被任何矩形覆盖
                for rect in rectangles:
                    if rect[0] <= x1 and x2 <= rect[2] and rect[1] <= y1 and y2 <= rect[3]:
                        area = (area + (x2 - x1) * (y2 - y1)) % MOD
                        break
        
        return area

public class Solution {
    public int RectangleArea(int[][] rectangles) {
        const int MOD = 1000000007;
        
        // 提取所有x坐标和y坐标
        var xSet = new SortedSet<int>();
        var ySet = new SortedSet<int>();
        
        foreach (var rect in rectangles) {
            xSet.Add(rect[0]);
            xSet.Add(rect[2]);
            ySet.Add(rect[1]);
            ySet.Add(rect[3]);
        }
        
        var xs = xSet.ToArray();
        var ys = ySet.ToArray();
        
        long area = 0;
        
        // 遍历每个可能的网格
        for (int i = 0; i < xs.Length - 1; i++) {
            for (int j = 0; j < ys.Length - 1; j++) {
                int x1 = xs[i], x2 = xs[i + 1];
                int y1 = ys[j], y2 = ys[j + 1];
                
                // 检查这个网格是否被任何矩形覆盖
                foreach (var rect in rectangles) {
                    if (rect[0] <= x1 && x2 <= rect[2] && 
                        rect[1] <= y1 && y2 <= rect[3]) {
                        area = (area + (long)(x2 - x1) * (y2 - y1)) % MOD;
                        break;
                    }
                }
            }
        }
        
        return (int)area;
    }
}

var rectangleArea = function(rectangles) {
    const MOD = 1e9 + 7;
    
    // 提取所有x坐标和y坐标
    const xSet = new Set();
    const ySet = new Set();
    
    for (const rect of rectangles) {
        xSet.add(rect[0]);
        xSet.add(rect[2]);
        ySet.add(rect[1]);
        ySet.add(rect[3]);
    }
    
    const xs = Array.from(xSet).sort((a, b) => a - b);
    const ys = Array.from(ySet).sort((a, b) => a - b);
    
    let area = 0;
    
    // 遍历每个可能的网格
    for (let i = 0; i < xs.length - 1; i++) {
        for (let j = 0; j < ys.length - 1; j++) {
            const x1 = xs[i], x2 = xs[i + 1];
            const y1 = ys[j], y2 = ys[j + 1];
            
            // 检查这个网格是否被任何矩形覆盖
            for (const rect of rectangles) {
                if (rect[0] <= x1 && x2 <= rect[2] && 
                    rect[1] <= y1 && y2 <= rect[3]) {
                    area = (area + (x2 - x1) * (y2 - y1)) % MOD;
                    break;
                }
            }
        }
    }
    
    return area;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)n为矩形数量，坐标离散化O(n log n)，网格遍历O(n²)，每个网格检查覆盖O(n)
空间复杂度O(n)存储离散化后的坐标数组

相关题目