LeetCode 598. 区间加法 II

2021-03-25 HGNULB 约 9 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 598. 区间加法 II

题意分析

有一个 m × n 的矩阵，初始全为 0。给定一批操作 ops，每个操作是一对数 [a, b]，含义是把左上角那块 a 行 b 列的子矩阵（即所有满足 0 <= i < a 且 0 <= j < b 的格子）整体加 1。执行完全部操作后，问矩阵中最大值出现了多少次——注意要的是个数，不是最大值本身。

这里有一处极强的结构约束：每个操作影响的区域都锚定在左上角 (0, 0)，只是长宽不同。也就是说，所有操作区域都是「从原点出发的矩形」，它们互相之间只有包含关系，绝不会出现错位重叠。这一条把问题的自由度压到了极低。

由此立刻可以推出：格子 (i, j) 最终的值，等于有多少个操作的矩形覆盖了它；而一个格子被覆盖得越多，值就越大。既然所有矩形都从左上角出发，越靠近左上角的格子被覆盖的次数就越多——严格地说，若格子 (i, j) 被某个操作覆盖，那么它左上方的所有格子（行号不大于 i、列号不大于 j）也必然被同一个操作覆盖。于是最大值必然出现在所有矩形的公共部分，也就是它们的交集里。

交集本身还是一个从左上角出发的矩形：行数是所有 a 的最小值，列数是所有 b 的最小值。而交集里的每个格子都被全部操作覆盖，取值一致且都等于操作数，正是全局最大值。所以答案就是这个交集的面积。

约束方面，m 与 n 可以很大（$10^4$ 级），而 ops 的长度也可能很大，但真正开一个 m × n 的矩阵去模拟是不必要的——$10^4 \times 10^4$ 是一亿个格子，内存和时间都不可接受。题目给出这样的规模，正是在暗示答案应当只与 ops 有关、与矩阵规模无关，即 $O(k)$ 时间、$O(1)$ 空间。

边界：ops 为空时一次操作都没有，整个矩阵全是 0，最大值 0 出现了 $m \times n$ 次——所以最小值的初值必须取 m 和 n，而不是某个大常数或第一个操作的值；题目保证 1 <= ai <= m、1 <= bi <= n，所以交集不会退化成空矩形。

解法：求所有操作的交集面积

核心思路

最直接的做法是老老实实模拟：开一个 m × n 的二维数组，对每个操作把对应的左上角区域逐格加一，最后扫一遍找最大值并计数。它一定对，但代价是 $O(k \cdot m \cdot n)$ 的时间和 $O(m \cdot n)$ 的空间——m、n 到 $10^4$ 时是一亿个格子乘以操作数，彻底不可行。

稍微改进一点，可以用二维差分把每次操作降到 $O(1)$，最后一次前缀和还原，总代价 $O(mn + k)$。这已经是个像样的算法，但空间仍是 $O(mn)$，而且它完全没有利用「所有矩形都锚定左上角」这个特殊性质——差分是为任意位置的矩形准备的通用工具，在这里属于杀鸡用牛刀。

真正的突破口是那条结构性质。每个操作的区域都是 [0, a) × [0, b)，起点固定。于是任意两个操作区域的关系只有包含，交集依然是从原点出发的矩形。把这个观察推广到全部 k 个操作：它们的交集就是 [0, min(a)) × [0, min(b))。

接下来论证「最大值恰好落在交集上」。设某个格子 (i, j) 在交集内，那么对每个操作都有 i < a 且 j < b，所以它被所有 k 个操作覆盖，取值为 k；而任何一个格子被覆盖的次数显然不超过操作总数 k，因此 k 就是全局最大值，交集内的每个格子都取到它。反过来，交集外的格子至少漏掉一个操作，取值最多 k - 1，严格更小。于是取最大值的格子集合恰好等于交集，一个不多、一个不少。

答案随之变成 $\min(a_i) \times \min(b_i)$，只需扫一遍 ops 求两个最小值。整个矩阵从头到尾都不需要建出来。

循环不变量：扫描到第 t 个操作时，minRow 等于前 t 个操作（外加初值 m）的行界最小值，minCol 同理。初值取 m 和 n，恰好表达了「零个操作时，全矩阵都是最大值区域」这个语义——ops 为空时循环不执行，直接返回 $m \times n$，边界自然落进主逻辑，不需要任何特判。

解题步骤

令 minRow = m、minCol = n。为什么：这两个初值同时承担了两个职责。其一是数学上的单位元——整个矩阵可以看作「一个覆盖全部区域的虚拟操作」，与它取交集不改变结果。其二是边界处理——ops 为空时循环一次都不进，直接返回 $m \times n$，正是「全矩阵都是 0、都是最大值」的正确答案。若初值取 Integer.MAX_VALUE，空 ops 会返回一个溢出的巨大数字。

遍历 ops，对每个 op 执行 minRow = min(minRow, op[0])、minCol = min(minCol, op[1])。为什么：所有操作区域都锚定在左上角，因此交集的行界就是各操作行界的最小值，列界同理；两个维度互相独立，可以分别取最小，不需要配对比较。这里只关心最小值，操作的顺序、重复与否都不影响结果。

返回 minRow * minCol。为什么：交集是 minRow 行 minCol 列的矩形，其中每个格子都被全部操作覆盖、取值相同且为全局最大；交集外的格子至少少被覆盖一次，严格更小。所以取最大值的格子数恰好是交集的面积。

以 m = 3, n = 3, ops = [[2,2], [3,3]] 走一遍。

初始 minRow = 3、minCol = 3。

第一个操作 [2, 2]：min(3, 2) = 2，minRow 更新为 2；min(3, 2) = 2，minCol 更新为 2。

第二个操作 [3, 3]：min(2, 3) = 2 不变；min(2, 3) = 2 不变。

返回 2 * 2 = 4。

手工验证一下：第一个操作给左上角 2×2 区域加 1，第二个操作给整个 3×3 加 1，最终矩阵是

[[2, 2, 1], [2, 2, 1], [1, 1, 1]]

最大值 2 出现在左上角的四个格子里，共 4 个，与答案一致。可以看到第二个操作虽然覆盖面更大，却完全没有改变答案——因为交集只由最小的那个矩形决定，更大的矩形是冗余约束。

再看空输入 ops = []：循环不执行，直接返回 3 * 3 = 9，对应全零矩阵中最大值 0 出现 9 次。这正是初值取 m、n 换来的好处——不需要写任何 if (ops.length == 0) 分支。

代码实现

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        // 初值取 m、n：既是交集的单位元，也让空 ops 自然返回 m * n。
        int minRow = m;
        int minCol = n;

        for (int[] op : ops) {
            // 所有操作区域都锚定左上角，两个维度可以各自独立取最小。
            minRow = Math.min(minRow, op[0]);
            minCol = Math.min(minCol, op[1]);
        }

        // 交集内的格子被全部操作覆盖，取值最大；交集外至少少覆盖一次。
        return minRow * minCol;
    }
}

func maxCount(m int, n int, ops [][]int) int {
    // 初值取 m、n：既是交集的单位元，也让空 ops 自然返回 m * n。
    minRow := m
    minCol := n

    for _, op := range ops {
        // 所有操作区域都锚定左上角，两个维度可以各自独立取最小。
        if op[0] < minRow {
            minRow = op[0]
        }
        if op[1] < minCol {
            minCol = op[1]
        }
    }

    // 交集内的格子被全部操作覆盖，取值最大；交集外至少少覆盖一次。
    return minRow * minCol
}

复杂度分析

时间复杂度：$O(k)$，k 为操作数。凭什么：只有一层循环扫过 ops，每个操作做两次比较和至多两次赋值，全是常数操作；矩阵本身从未被访问，所以复杂度与 m、n 完全无关。这正是本题相对「二维差分 + 前缀和」（$O(mn + k)$）的关键优势。

空间复杂度：$O(1)$。凭什么：只用了 minRow、minCol 两个整型变量，没有开任何数组；输入 ops 是给定数据，不计入辅助空间。相比之下模拟法需要 $O(mn)$ 的矩阵，在 $10^4 \times 10^4$ 的规模下根本开不出来。

关键点总结

看到「最大值出现多少次」而不是「最大值是多少」，要立刻意识到答案是一个集合的大小，问题会转化为刻画这个集合的形状，而不是真的去求值。

本题的全部威力来自「所有操作区域共享同一个锚点」。锚点固定 ⇒ 区域之间只有包含关系 ⇒ 交集仍是同类矩形 ⇒ 取最小值即可。凡是遇到「所有区间/矩形都从同一端点出发」的题，都该先找这条捷径，而不是直接上差分或线段树。

「被覆盖次数最多的格子取值最大」这一步要能说清楚：因为每次操作的增量都是 +1 且相同，值与覆盖次数严格同增。若各操作的增量不同，这个等价关系就不成立，解法也要换。

用单位元当初值是消除边界分支的通用技巧。这里 minRow = m 相当于引入一个「覆盖全矩阵的虚拟操作」，空输入立刻退化成正确答案，不需要任何 if 判断。反之若用 Integer.MAX_VALUE 做初值，空输入会直接溢出。

识别出「暴力模拟 $O(kmn)$ → 二维差分 $O(mn + k)$ → 数学观察 $O(k)$」这条优化链，并说明每一步省掉了什么，是这类题在面试中的正确答法。只给最终结论会让人怀疑是背下来的。

面试延伸：若追问「操作区域改成任意位置的矩形怎么办」，答案是二维差分——每个操作在四个角上打标记，最后做二维前缀和还原，$O(mn + k)$；若再追问「还要支持中途查询」，则需要二维树状数组或线段树。

易错点总结

初值取 Integer.MAX_VALUE（或很大的常数）：ops = [] → 循环不执行，返回 MAX_VALUE * MAX_VALUE，乘法溢出成一个负数或无意义的值，正确答案是 $m \times n$。

初值取 0：任意输入 → min 永远是 0，直接返回 0；m = 3, n = 3, ops = [[2,2]] 应返回 4。

初值取第一个操作的值却没处理空数组：ops = [] → 访问 ops[0] 直接数组越界。

返回最大值本身而不是它的出现次数：m = 3, n = 3, ops = [[2,2],[3,3]] → 返回 2（最大值），正确答案是 4（出现次数）。

取最大值而不是最小值：同一输入 → maxRow = 3、maxCol = 3，返回 9；但被全部操作覆盖的只有左上角 2×2 那块，正确答案是 4。

把两个维度配对比较（按面积取最小的那个操作）：ops = [[1, 5], [5, 1]] → 两个操作面积相同，按面积挑会保留其中一个得到 5，而真实交集是 1 × 1 = 1；两个维度必须各自独立取最小。

真的开一个 m × n 的矩阵模拟：m = n = 10^4 → 一亿个格子，内存直接爆掉；即便勉强开出来，逐格加一也会超时。

认为「面积最小的操作」就是交集：ops = [[1, 5], [5, 1]] 中面积最小的是 5，但答案是 1 → 交集由两个维度分别取最小得到，未必等于任何一个给定的操作。

误以为操作区域是 [a, m) × [b, n)（右下角）：m = 3, n = 3, ops = [[2,2]] → 会去求最大值而不是最小值，返回 1 而非 4；题目明确是左上角的 a 行 b 列。

把 a、b 当成下标而不是长度：ops = [[2,2]] → 认为覆盖的是 [0, 2] 共 3 行 3 列，返回 9；题目的 a 是行数，覆盖的是 0 到 a - 1。

相似题目

题目	难度	考察点
370. 区间加法	中等	一维版且区间位置任意，无法取交集，必须用差分数组把每次操作降到 $O(1)$
1109. 航班预订统计	中等	370 的典型应用，考的是差分数组的边界下标与最终前缀和还原
1094. 拼车	中等	差分之外还要在还原过程中随时校验容量上限，是差分 + 扫描线的结合
223. 矩形面积	中等	同为矩形求交，但两个矩形位置任意，交集要在两个维度上分别做区间相交
836. 矩形重叠	简单	只判断是否相交而不求面积，可用「反向排除四种不相交情形」一步得出
304. 二维区域和检索 - 矩阵不可变	中等	同样利用「从左上角出发」的性质，但方向相反：用二维前缀和支持任意子矩阵查询
56. 合并区间	中等	区间位置任意且要求并集而非交集，需先排序再线性扫描合并
253. 会议室 II	中等	求的是「最大重叠层数」，靠扫描线或最小堆统计同时活跃的区间数