LeetCode 850. 矩形面积 II

2024-05-22 HGNULB 约 14 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 850. 矩形面积 II

题意分析

给一批轴对齐的矩形，每个写成 [x1, y1, x2, y2]，表示左下角和右上角。要求它们并集的总面积，重叠部分只能算一次，结果对 $10^9 + 7$ 取模。

「并集」两个字排除了最直白的做法：把每个矩形的面积加起来再减去重叠。容斥原理在这里需要枚举所有非空子集，矩形数量最多 200 个，$2^{200}$ 完全不可行。

规模上的两个数字方向相反，构成了这道题的核心张力：矩形只有 200 个，非常少；但坐标范围是 $0$ 到 $10^9$，非常大。少的那一维暗示可以做平方甚至更高次的处理，大的那一维则宣告了「按单位格子统计」这种做法必死——面积本身就能达到 $10^{18}$ 量级。

坐标大而点少，标准应对就是离散化：真正起作用的只有各矩形边界所在的那些坐标值，中间的连续区段内部一切性质都不变。

「结果取模」是个陷阱信号。取模的只有最终答案，中间过程中的「当前覆盖长度」和「横向跨度」都必须保持真值，两者相乘可以达到 $10^{18}$，必须用 64 位整数承接，绝不能先取模再相乘。

边界上要留意：题目保证 $x_1 < x_2$、$y_1 < y_2$，不存在退化成线段的矩形；但不同矩形完全可能共享边界坐标，离散化后必须去重，否则会产生长度为零的区间。

解法：扫描线 + 线段树

核心思路

先想一个可行但慢的做法。既然坐标可以离散化，那就把所有出现过的 $x$ 值排序去重得到 $x_0 < x_1 < \dots$，所有 $y$ 值同样处理，于是整个平面被切成若干个小矩形格。格子总数是 $O(n^2)$，即 $400 \times 400 = 1.6 \times 10^5$ 个。对每个格子判断它是否被至少一个矩形覆盖，是则把它的真实面积加进答案。判断一个格子要遍历 200 个矩形，总代价 $O(n^3) = 3.2 \times 10^7$——其实这个做法在本题数据下能过，而且很好写。

但它有个明显的浪费：同一条竖直细带（相邻两个 $x$ 之间的区域）内，覆盖情况沿 $y$ 方向是完全静态的，我们却对带内每个格子都重新扫了一遍所有矩形。

把这个浪费消掉，就得到扫描线。想象一条竖直的线从左往右扫过平面。在两个相邻的「事件 $x$ 坐标」之间，被覆盖的 $y$ 集合完全不变，所以这一段贡献的面积就是「当前被覆盖的 $y$ 总长度」乘以「这段横向跨度」。整个面积于是被拆成若干个这样的矩形条带之和。

事件是什么？每个矩形 [x1, y1, x2, y2] 产生两条竖边：在 $x = x_1$ 处，区间 $[y_1, y_2]$ 进入覆盖，记为 $+1$；在 $x = x_2$ 处，同一区间离开覆盖，记为 $-1$。把 $2n$ 条事件按 $x$ 排序，依次处理即可。

剩下的问题是：如何在支持「区间 $+1$ / 区间 $-1$」的同时，$O(\log n)$ 地查询「当前被至少覆盖一次的总长度」。这正是线段树的一个经典变体。把去重后的 $y$ 坐标记为 $ys[0..m-1]$，线段树的叶子不是这些坐标点本身，而是相邻两点之间的区间 $[ys[i], ys[i+1])$，共 $m-1$ 个。每个节点维护两个量：count 表示「整段被完整覆盖了多少次」，len 表示「这段内部被至少覆盖一次的真实长度」。

关键的合并规则（也是这棵树最反直觉的地方）：如果一个节点的 count > 0，说明整段都被盖住了，len 直接等于该节点对应的坐标跨度 $ys[r] - ys[l]$，不用看子节点；否则 len 等于两个子节点的 len 之和，叶子节点则为 $0$。注意 count 不下传——它记录的是「恰好在这一层被完整覆盖的次数」，是一个原地语义，一旦下传就会丢失「本层被整段覆盖」这个信息，len 也就算不对了。

于是维护的不变量是：处理完所有 $x$ 值不超过某个位置的事件后，线段树根节点的 len 恒等于「此刻扫描线上被矩形覆盖的 $y$ 总长度」，而累加器 area 恒等于「所有 $x$ 小于当前扫描位置的区域内，并集的真实面积（对模数取余）」。

解题步骤

为每个矩形生成两条事件：(x1, y1, y2, +1) 和 (x2, y1, y2, -1)，同时把 $y_1$、$y_2$ 收进 $y$ 坐标池。为什么用左加右减：这样任意时刻的 count 恰好等于「跨过当前扫描线的矩形中，覆盖该段的个数」。

把 $y$ 坐标池排序并去重，得到严格递增的 coords。为什么必须去重：重复坐标会产生长度为零的叶子区间，既浪费空间，也会让二分查找的返回值失去唯一性。

按 $x$ 从小到大排序所有事件。为什么只按 $x$ 排、不管加减顺序：同一个 $x$ 上的多个事件之间横向跨度为零，无论怎么排都不贡献面积，只要保证「结算在前、更新在后」即可。

建线段树，叶子对应相邻坐标之间的区间，count 和 len 全部初始化为 $0$。

依次处理每条事件。先用当前根节点的 len 乘以 x - prevX 累加进 area 并取模，再把本条事件的区间增量更新进树，最后把 prevX 推进到 x。为什么必须是这个顺序：area 结算的是「上一个事件位置到当前位置」这段带子，这段带子里的覆盖状态是本次更新之前的状态，先更新就等于让新矩形穿越了它还没到达的区域。

区间更新时用二分在 coords 里找到 $y_1$ 和 $y_2$ 的下标 $l$、$r$，更新的是下标区间 $[l, r)$。为什么是左闭右开：叶子代表的是相邻坐标之间的区间，$y$ 值从 $ys[l]$ 到 $ys[r]$ 对应的正是第 $l$ 到第 $r-1$ 号区间。

更新递归里，完全覆盖的节点直接把 val 累加进 count 后重算 len，部分相交的节点则递归左右子树后再重算。为什么每次都要重算 len：count 可能从正数降到 $0$，此时该节点必须重新从子节点合并出真实长度。

遍历结束后返回累加结果。

以 rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] 走一遍：事件依次是 $(0,[0,2],+1)$、$(2,[0,2],-1)$、$(1,[0,3],+1)$、$(2,[0,3],-1)$、$(1,[0,1],+1)$、$(3,[0,1],-1)$。$y$ 坐标池是 ${0,2,0,3,0,1}$，排序去重后 coords = [0, 1, 2, 3]，三个叶子区间分别是 $[0,1)$、$[1,2)$、$[2,3)$。按 $x$ 排序后事件序列为：$x=0$ 加 $[0,2]$；$x=1$ 加 $[0,3]$；$x=1$ 加 $[0,1]$；$x=2$ 减 $[0,2]$；$x=2$ 减 $[0,3]$；$x=3$ 减 $[0,1]$。初始 prevX = 0、area = 0、根 len = 0。

第一条事件 $x=0$：先结算 $0 \times (0-0) = 0$；再把下标区间 $[0, 2)$ 加 1，覆盖 $y \in [0,2]$，根 len 变成 2。prevX = 0。第二条事件 $x=1$：先结算 $2 \times (1-0) = 2$，area = 2；再把 $[0, 3)$ 加 1，覆盖扩展到 $y \in [0,3]$，根 len 变成 3。prevX = 1。第三条事件 $x=1$：先结算 $3 \times (1-1) = 0$；再把 $[0, 1)$ 加 1，覆盖范围不变，根 len 仍是 3。prevX = 1。第四条事件 $x=2$：先结算 $3 \times (2-1) = 3$，area = 5；再把 $[0,2)$ 减 1，撤掉第一个矩形，但第二个矩形仍覆盖 $[0,3]$，根 len 保持 3。prevX = 2。第五条事件 $x=2$：先结算 $3 \times (2-2) = 0$；再把 $[0,3)$ 减 1，只剩第三个矩形覆盖 $[0,1]$，根 len 降为 1。prevX = 2。第六条事件 $x=3$：先结算 $1 \times (3-2) = 1$，area = 6；再把 $[0,1)$ 减 1，根 len 归零。返回 $6$。

代码实现

// 线段树维护当前 x 段内被覆盖的 y 总长度。
class Solution {
    private static final int MOD = 1_000_000_007;

    public int rectangleArea(int[][] rectangles) {
        List<int[]> events = new ArrayList<>();
        List<Integer> ys = new ArrayList<>();

        for (int[] r : rectangles) {
            events.add(new int[]{r[0], r[1], r[3], 1});
            events.add(new int[]{r[2], r[1], r[3], -1});
            ys.add(r[1]);
            ys.add(r[3]);
        }

        ys.sort(Integer::compareTo);
        List<Integer> uniq = new ArrayList<>();
        for (int y : ys) {
            if (uniq.isEmpty() || uniq.get(uniq.size() - 1) != y) {
                uniq.add(y);
            }
        }

        int[] coords = new int[uniq.size()];
        for (int i = 0; i < uniq.size(); i++) {
            coords[i] = uniq.get(i);
        }

        events.sort(Comparator.comparingInt(a -> a[0]));
        SegmentTree tree = new SegmentTree(coords);

        long area = 0;
        int prevX = events.get(0)[0];
        for (int[] e : events) {
            int x = e[0];
            long cover = tree.totalLen();
            area = (area + cover * (x - prevX)) % MOD;

            int y1 = e[1];
            int y2 = e[2];
            int type = e[3];
            int l = Arrays.binarySearch(coords, y1);
            int r = Arrays.binarySearch(coords, y2);
            tree.update(l, r, type, 1, 0, coords.length - 1);

            prevX = x;
        }

        return (int) area;
    }

    private static class SegmentTree {
        private final int[] ys;
        private final int[] count;
        private final long[] len;

        SegmentTree(int[] ys) {
            this.ys = ys;
            int n = ys.length * 4;
            this.count = new int[n];
            this.len = new long[n];
        }

        long totalLen() {
            return len[1];
        }

        void update(int ql, int qr, int val, int idx, int l, int r) {
            if (ql >= r || qr <= l) {
                return;
            }
            if (ql <= l && r <= qr) {
                count[idx] += val;
                pushUp(idx, l, r);
                return;
            }

            int mid = (l + r) / 2;
            update(ql, qr, val, idx * 2, l, mid);
            update(ql, qr, val, idx * 2 + 1, mid, r);
            pushUp(idx, l, r);
        }

        void pushUp(int idx, int l, int r) {
            if (count[idx] > 0) {
                len[idx] = ys[r] - ys[l];
                return;
            }
            if (l + 1 >= r) {
                len[idx] = 0;
                return;
            }
            len[idx] = len[idx * 2] + len[idx * 2 + 1];
        }
    }
}

// 线段树维护当前 x 段内被覆盖的 y 总长度。
func rectangleArea(rectangles [][]int) int {
    const mod int64 = 1_000_000_007
    type event struct {
        x   int
        y1  int
        y2  int
        typ int
    }

    events := make([]event, 0)
    ys := make([]int, 0)

    for _, r := range rectangles {
        events = append(events, event{x: r[0], y1: r[1], y2: r[3], typ: 1})
        events = append(events, event{x: r[2], y1: r[1], y2: r[3], typ: -1})
        ys = append(ys, r[1], r[3])
    }

    sort.Ints(ys)
    coords := make([]int, 0)
    for _, y := range ys {
        if len(coords) == 0 || coords[len(coords)-1] != y {
            coords = append(coords, y)
        }
    }

    sort.Slice(events, func(i, j int) bool { return events[i].x < events[j].x })
    seg := newSegTree(coords)

    area := int64(0)
    prevX := events[0].x
    for _, e := range events {
        x := e.x
        cover := seg.totalLen()
        area = (area + cover*int64(x-prevX)) % mod

        l := sort.SearchInts(coords, e.y1)
        r := sort.SearchInts(coords, e.y2)
        seg.update(l, r, e.typ, 1, 0, len(coords)-1)

        prevX = x
    }

    return int(area)
}

type segTree struct {
    ys    []int
    count []int
    len   []int64
}

func newSegTree(ys []int) *segTree {
    n := len(ys) * 4
    return &segTree{ys: ys, count: make([]int, n), len: make([]int64, n)}
}

func (t *segTree) totalLen() int64 {
    return t.len[1]
}

func (t *segTree) update(ql int, qr int, val int, idx int, l int, r int) {
    if ql >= r || qr <= l {
        return
    }
    if ql <= l && r <= qr {
        t.count[idx] += val
        t.pushUp(idx, l, r)
        return
    }
    mid := (l + r) / 2
    t.update(ql, qr, val, idx*2, l, mid)
    t.update(ql, qr, val, idx*2+1, mid, r)
    t.pushUp(idx, l, r)
}

func (t *segTree) pushUp(idx int, l int, r int) {
    if t.count[idx] > 0 {
        t.len[idx] = int64(t.ys[r] - t.ys[l])
        return
    }
    if l+1 >= r {
        t.len[idx] = 0
        return
    }
    t.len[idx] = t.len[idx*2] + t.len[idx*2+1]
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 $n$ 是矩形数量。生成 $2n$ 条事件是线性的；对事件按 $x$ 排序、对 $y$ 坐标排序去重各是 $O(n \log n)$；随后每条事件做一次区间更新，线段树只有 $O(n)$ 个叶子，单次更新触及 $O(\log n)$ 个节点，$2n$ 条事件合计 $O(n \log n)$；查询根节点的覆盖长度是 $O(1)$。

空间复杂度：$O(n)$。事件数组有 $2n$ 项，离散化坐标最多 $2n$ 个，线段树按四倍开辟也是 $O(n)$ 个节点，递归深度 $O(\log n)$ 可忽略。

关键点总结

扫描线的本质是降维积分：把二维面积写成「一维测度沿另一维的累加」。凡是「求并集面积 / 周长 / 覆盖轮廓」的题，第一反应都应该是找出会让一维测度发生变化的那些事件点。

坐标范围大而关键点少时，离散化是标配。但要分清离散化的对象——本题线段树的叶子是相邻坐标之间的区间而不是坐标点，长度是 $ys[i+1] - ys[i]$ 而不是 1，这是初学者最容易搞错的地方。

这棵线段树的 count 不做懒惰下传。因为 count 的语义是「在本层被完整覆盖的次数」，下传会破坏这个语义。它能不下传的前提是所有更新都成对出现（加了必然减回来），因此 count 永远非负，不会出现「减到负数」的病态节点。

「先结算旧状态、再更新新事件」是所有扫描线代码的固定骨架。写反了不会崩溃，只会静默地把面积算错一个条带，非常难查。

中间量必须用 64 位。覆盖长度可达 $10^9$，横向跨度也可达 $10^9$，乘积是 $10^{18}$；只对累加结果取模，绝不能对参与乘法的因子取模。

面试视角：这题在白板上写完整棵线段树几乎不现实。更稳妥的答法是先给出 $O(n^3)$ 的坐标离散化 + 逐格判定（$n \le 200$ 时可以通过），点明它的浪费在哪，再口述扫描线 + 线段树的结构与两个维护量，最后视时间决定要不要落实到代码。

易错点总结

错误写法：先把事件更新进线段树，再结算面积。用例 [[0,0,2,2],[1,0,2,3],[1,0,3,1]] 中，处理 $x=1$ 的事件时会用扩展后的覆盖长度 3 去乘 $x$ 从 0 到 1 的跨度，把还不存在的矩形算进了 $[0,1]$ 这一条带，答案偏大。

错误写法：线段树的叶子按坐标点建，len 用「被覆盖的点数」表示。用例里 coords = [0,1,2,3] 有 4 个点却只有 3 个区间，覆盖 $[0,3]$ 会算成 4 而不是 3，面积整体偏大。

错误写法：pushUp 里当 count > 0 时设置 len，count == 0 时却直接返回不做任何处理。矩形离开后 len 仍停留在旧值，用例中 $x=2$ 撤掉第一个矩形后覆盖长度不再收缩，后续条带全部算大。

错误写法：把 count 当成普通的区间加法标记做懒惰下传。下传后父节点失去「本层整段被覆盖」的信息，len 的合并规则失效，结果不可预测。

错误写法：area 或 cover 用 32 位整型。覆盖长度和横向跨度都能达到 $10^9$，乘积溢出后会变成负数或随机值，大坐标用例上直接错。

错误写法：对参与乘法的 cover 先取模。取模改变的是数值本身，cover 是真实几何长度，取模后乘出来的不再是这一条带的面积。只有最终累加值才能取模。

错误写法：$y$ 坐标排序后忘记去重。相邻相同坐标会产生长度为零的叶子，二分查找也无法确定该返回哪一个下标，区间边界会错位。

错误写法：线段树数组只开 $2m$ 或 $3m$。递归建树在非完全二叉的形状下需要四倍空间，开小了会在深层节点处越界。

错误写法：区间更新时把下标区间当成闭区间 $[l, r]$。这会多覆盖一个叶子，也就是多算 $ys[r+1] - ys[r]$ 这段长度，用例中会把 $y \in [2,3]$ 也算进第一个矩形。

错误写法：用容斥原理，把所有矩形面积相加再逐对减去交集。三个及以上矩形共同重叠的区域会被反复加减，用例 [[0,0,2,2],[1,0,2,3],[1,0,3,1]] 里三者在 $[1,2] \times [0,1]$ 上共同重叠，只减两两交会把它多减一次，答案偏小。

相似题目

题目	难度	考察点
218. 天际线问题	困难	同为扫描线，但维护的是「当前最大高度」而非覆盖长度，用多重集或最大堆即可，且需要输出高度发生变化的拐点
391. 完美矩形	困难	同样处理矩形并集，但只需判定是否恰好拼成一个大矩形，用「面积之和相等 + 角点出现次数的奇偶性」即可，不需要线段树
223. 矩形面积	中等	退化到两个矩形，交集可以直接用区间取交算出，考察的是容斥公式和边界不相交时的处理