LeetCode 850. 矩形面积 II

2024-05-22 HGNULB 约 10 分钟

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

分类

LeetCode CodeTop 困难未解决 2-5 阿里美团

题目描述

✅ 850. 矩形面积 II

题意分析

求所有轴对齐矩形覆盖的总面积，无论重叠多少次都只计一次，最后对 $10^9+7$ 取模。坐标可达 $10^9$，不能逐格枚举；覆盖情况只会在矩形边界处改变，可以按这些边界划分条带。

解法：扫描线 + 线段树

核心思路

[!blue]

从左向右移动一条竖直扫描线。矩形左边界产生加入事件，右边界产生移除事件，事件维护该矩形的纵向区间 [y1, y2)。相邻两个事件横坐标之间没有矩形加入或退出，所以纵向覆盖集合不变，这条竖带的面积就是“纵向并集长度 × 横向宽度”。半开区间只用于明确边界归属，不影响连续平面的面积。

将全部纵坐标排序去重为 coords。相邻坐标之间不会再有矩形边界，可以把每段 [coords[i], coords[i + 1]) 作为线段树的一个叶子。节点的下标区间 [l, r) 对应真实范围 [coords[l], coords[r])；若有 m 个不同坐标，根的下标范围就是 [0, m - 1)，而不是把坐标点本身作为叶子。

每个节点保存 count 和 len。count 只统计区间更新完整覆盖当前节点、因而停在当前层的活动覆盖次数；它不是该段所有覆盖次数的总和。len 则表示由当前节点及其后代记录的覆盖贡献所形成的并集长度。若 count > 0，整段已被覆盖，len = coords[r] - coords[l]；若 count == 0 且为叶子，长度为 0；否则用两个孩子的长度之和恢复局部覆盖。

更新与节点无交集时跳过，完全覆盖时只调整当前层 count，部分相交时递归更新孩子，再重新计算 len。即使当前节点 count > 0，局部更新也不能省略：父层的整段覆盖日后可能被移除，那时必须依靠孩子已经记录的变化恢复正确长度。重复矩形只增加覆盖次数，不会重复增加长度；移除一份后只要还有覆盖，长度就仍然保留。

扫描到横坐标 x 时，树根的 len 描述的是上一条竖带，因此先累加 len × (x - prevX)，再应用当前事件。相同横坐标的事件之间宽度为 0，可以依次处理；全部处理完后的覆盖用于下一条竖带。坐标和覆盖长度保留精确值，只对面积累计取模。单次乘积至多为 $10^{18}$，使用 64 位整数计算即可。

解题步骤

每个矩形生成两个事件 (x1, y1, y2, +1)、(x2, y1, y2, -1)，并收集纵坐标边界。

将纵坐标排序去重，建立维护相邻坐标区间的线段树；按横坐标排序事件。

将 prevX 设为首个事件的横坐标。树初始无覆盖，因此首次结算面积为 0。

对每个事件，先用树根长度结算 [prevX, x) 的面积，再二分查找 y1、y2 的下标，将对应半开区间的覆盖次数增减 1，最后更新 prevX。

最右边界处理完后，所有可能有面积的条带均已结算，返回累计结果。

代码实现

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];
        }
    }
}

import "sort"

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+1))$，其中 $N$ 为矩形数量。共有 $2N$ 个事件和至多 $2N$ 个纵坐标；排序后，每个事件的坐标查找与区间更新均为 $O(\log(N+1))$。

空间复杂度：$O(N)$，用于事件、离散坐标和线段树数组。

关键点总结

[!green]

离散叶子是坐标间的区间，长度不是下标差。

同横坐标事件之间跨度零，处理后再用于下一个条带。

count 保存当前层的整段覆盖，孩子保存局部覆盖，两者都要保留，才能在移除矩形时正确恢复长度。

面积乘法使用宽整数，取模只作用于面积累计，不能改动用于几何比较的原始坐标。

易错点总结

[!yellow]

先更新事件再结算，会让新覆盖提前作用到上一条带。

移除后不重新合并长度，会保留旧覆盖。

只做两两重叠扣除，无法正确处理三重及更多重叠。

相似题目

题目	难度	关联与区别
391. 完美矩形	困难	原题判断矩形能否无缝无重叠覆盖一个大矩形，本题允许任意重叠并计算并集面积。
223. 矩形面积	中等	矩形并面积系列。I 是两个矩形的基础情形，可直接求交集；II 处理多个矩形的重叠并集。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2024/96547520

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！