T850.矩形面积 II

Sweep Line Algorithm, Coordinate Compression, https://leetcode.cn/problems/rectangle-area-ii/

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

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

返回 总面积 。因为答案可能太大，返回 109 + 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
解释：答案是 1018 对 (109 + 7) 取模的结果， 即 49 。

提示：

1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= xi1, yi1, xi2, yi2 <= 10^9
xi1 <= xi2
yi1 <= yi2
所有矩阵面积不为 0。

这道题的核心在于处理多个矩形的重叠面积。由于坐标范围很大（高达 $10^{9}$ ），直接使用二维网格标记是不现实的。但注意到矩形数量较少（最多 200 个），我们可以采用 扫描线法（Sweep Line Algorithm） 配合 离散化（Coordinate Compression） 来解决。

解题思路

扫描线 + 离散化：
- 我们将所有的垂直边（即矩形的左边界 $x_{1}$ 和右边界 $x_{2}$ ）提取出来并排序，这些 $x$ 坐标将整个平面切割成若干个垂直的条带（Strips）。
- 在两个相邻的 $x$ 坐标 $[x_{i}, x_{i + 1}]$ 构成的条带内，所有矩形的覆盖情况在水平方向上是相同的。
- 我们只需要计算每个条带内，在 $y$ 轴方向上被覆盖的总长度，乘以条带的宽度 $(x_{i + 1} - x_{i})$ ，即可得到该条带的面积。
具体步骤：
- 提取 $x$ 坐标：搜集所有矩形的 $x_{1}$ 和 $x_{2}$ ，排序并去重。
- 遍历条带：遍历每一对相邻的 $x$ 坐标。
- 筛选 $y$ 区间：对于当前的条带 $[x_{i}, x_{i + 1}]$ ，找出所有覆盖了该条带范围的矩形（即满足 $r e c t . x 1 \leq x_{i}$ 且 $r e c t . x 2 \geq x_{i + 1}$ 的矩形），记录它们的 $y$ 轴区间 $[y_{1}, y_{2}]$ 。
- 计算 $y$ 轴并集长度：将这些 $y$ 区间排序，合并重叠部分，计算出总覆盖长度。
- 累加面积：条带面积 = 并集长度 $\times (x_{i + 1} - x_{i})$ 。
- 取模：最后对 $10^{9} + 7$ 取模。

复杂度分析

时间复杂度： $O (N^{2} \log N)$ 。其中 $N$ 是矩形数量。
- $x$ 轴排序需要 $O (N \log N)$ 。
- 外层循环遍历条带，共约 $2 N$ 次。
- 内层遍历矩形筛选 $y$ 区间 $O (N)$ ，对 $y$ 区间排序 $O (N \log N)$ 。
- 总计 $O (N^{2} \log N)$ 。当 $N = 200$ 时，计算量约几十万次，Python 可以轻松通过。
空间复杂度： $O (N)$ ，用于存储 $x$ 坐标和 $y$ 区间。

Python 代码实现

python

from typing import List

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # 1. 收集并排序所有唯一的 x 坐标，将平面划分为垂直条带
        x_coords = sorted(set([r[0] for r in rectangles] + [r[2] for r in rectangles]))
        
        total_area = 0
        
        # 2. 遍历每一个垂直条带 [x_start, x_end]
        for i in range(len(x_coords) - 1):
            x_start, x_end = x_coords[i], x_coords[i+1]
            width = x_end - x_start
            if width == 0:
                continue
            
            # 3. 找出所有覆盖当前垂直条带的矩形的 y 区间
            y_intervals = []
            for rx1, ry1, rx2, ry2 in rectangles:
                if rx1 <= x_start and rx2 >= x_end:
                    y_intervals.append((ry1, ry2))
            
            if not y_intervals:
                continue
            
            # 4. 计算 y 区间的并集长度
            # 先按起始位置排序
            y_intervals.sort()
            
            union_len = 0
            curr_max_y = -1
            for y1, y2 in y_intervals:
                # 如果当前区间的终点超过了已覆盖的最大高度，说明有新覆盖区域
                if y2 > curr_max_y:
                    # 增加的部分是 y2 减去 (当前起始位置 y1 和 已覆盖最大高度 的较大者)
                    union_len += y2 - max(y1, curr_max_y)
                    curr_max_y = y2
            
            # 5. 累加当前条带的面积
            total_area += union_len * width
            
        return total_area % MOD

代码要点说明

y 轴合并技巧：在计算 union_len 时，我们维护一个 curr_max_y。由于 y_intervals 已经按起点排序，如果当前区间的 y2 大于 curr_max_y，那么 y2 - max(y1, curr_max_y) 就能准确算出这段区间对总长度的“净贡献”。
效率：这种算法在 $N$ 较小时（如本题 $N = 200$ ）非常高效。如果 $N$ 达到 $10^{5}$ 级别，则需要配合线段树来动态维护 $y$ 轴的覆盖长度，将复杂度降低到 $O (N \log N)$ 。但在本题场景下，上述写法更简洁易懂。

T850.矩形面积 II ​

T850.矩形面积 II