LeetCode 598. Range Addition II 题解：矩形交集法统计矩阵最大整数的个数
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本文基于 LeetCode-Go 仓库中的 0598.Range-Addition-II 题解，深入讲解 LeetCode 第 598 题「Range Addition II」的求解思路与 Go 实现。该题给定一个初始全零的 m×n 矩阵和一系列以左上角为原点的矩形更新操作，要求统计所有操作结束后矩阵中最大整数出现的个数。读完本文，你将掌握"矩形交集（求最小宽高）"这一核心优化思想，理解为什么这道看似需要线段树/差分数组的题可以做到 O(k) 时间、O(1) 空间，并能直接使用仓库中的源码与测试用例进行验证。
题目回顾与核心定义
题目原文要求（见 原题文档）：
给定一个 m * n 矩阵M，初始元素全部为 0，以及一系列更新操作。每个操作由两个正整数 a 和 b 表示，含义是将所有满足
0 <= i < a且0 <= j < b的元素M[i][j]的值都增加 1。执行完所有操作后，返回矩阵中最大整数的元素个数。
关键点在于：每个操作作用的都是一个矩形区域，且该矩形的左上角始终锚定在矩阵原点 (0, 0)。也就是说，每次操作影响的都是"从矩阵左上角出发、宽为 a、高为 b"的一个子矩形。
官方示例逐步推演
以m = 3, n = 3，operations = [[2,2],[3,3]]为例：
- 初始矩阵 M：
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]- 执行操作
[2,2]（第 0、1 行与第 0、1 列加 1）：
[[1, 1, 0], [1, 1, 0], [0, 0, 0]]- 执行操作
[3,3]（全部元素加 1）：
[[2, 2, 1], [2, 2, 1], [1, 1, 1]]最终最大整数为 2，共出现 4 次（即左上角 2×2 区域），答案为 4。
题目约束（决定算法选型）
- m 和 n 的范围是
[1, 40000]； - 每个操作中 a 的范围是
[1, m]，b 的范围是[1, n]； - 操作数目不超过 10000。
m, n最大可达 40000，意味着矩阵最多有1.6×10⁹ 个格子。若采用"逐格模拟"或"二维差分数组"的朴素思路，无论是时间还是空间都无法承受，这从约束上就决定了必须寻找纯数学/几何解法。
解题思路：矩形交集与最小宽高收缩
从"线段树区间覆盖"到"矩形交集"
仓库题解原文中特别提到（README.md）：
这一题乍一看像线段树的区间覆盖问题，但是实际上很简单。如果此题是任意的矩阵，那就可能用到线段树了。这一题每个矩阵的起点都包含 [0, 0] 这个元素，也就是说每次操作都会影响第一个元素。那么这道题就很简单了。
这句话点破了本题的本质：如果每个操作的矩形可以出现在矩阵的任意位置，那么这就是一个典型的"矩形区域最大覆盖次数"问题，确实需要二维差分、扫描线甚至线段树等重型手段；但本题的矩形全部"钉死"在原点 (0,0)，使得问题发生了质的简化。
为什么只需关心矩形的右下角
观察可以发现两条重要事实：
- 最大整数一定出现在操作次数最多的格子。每个格子的值等于覆盖它的操作次数，因此"最大值"就是"最大覆盖次数"。
- 所有操作矩形都包含原点 (0,0)。这意味着原点是覆盖次数最高的格子之一，且任何被所有操作共同覆盖的格子，其覆盖次数就是操作总数（全局最大）。
因此，题目要求的"最大整数的元素个数"，实际上就是所有操作矩形两两交集（也是全体交集）的面积。由于所有矩形共享左上角 (0,0)，它们的交集仍然是一个左上角在原点、宽高分别为"所有 a 的最小值"和"所有 b 的最小值"的矩形：
- 交集宽度 =
min(所有操作的 a, m)； - 交集高度 =
min(所有操作的 b, n)； - 最大整数个数 = 交集宽度 × 交集高度。
仓库题解对此的表述是（README.md）：
经过 n 次操作以后，被覆盖次数最多的矩形区间，一定就是最大整数所在的区间。由于起点都是第一个元素，所以我们只用关心矩形的右下角那个坐标。右下角怎么计算呢？只用每次动态的维护一下矩阵长和宽的最小值即可。
"动态维护矩阵长和宽的最小值"正是下面实现的核心动作。
Go 实现与逐步注释
仓库中的核心实现位于 598. Range Addition II.go：
package leetcode func maxCount(m int, n int, ops [][]int) int { minM, minN := m, n for _, op := range ops { minM = min(minM, op[0]) minN = min(minN, op[1]) } return minM * minN } func min(a, b int) int { if a < b { return a } return b }代码逻辑只有三步：
- 初始化：将
minM、minN初始化为矩阵本身的长宽m、n。这一步天然处理了边界情况——若ops为空，则没有任何操作，最大整数就是初始的 0，其个数为整个矩阵的面积m * n，此时minM * minN = m * n，结果正确。 - 遍历收缩：对每个操作
op，用op[0]（即 a）更新minM、用op[1]（即 b）更新minN，始终保持二者为已见过的所有 a、b 中的最小值。由于题目保证a <= m、b <= n，所以minM、minN不会超过矩阵边界，无需再与 m、n 额外取 min。 - 返回面积：
minM * minN即为最大整数出现的次数。
边界情况分析
| 场景 | 行为 | 结果 |
|---|---|---|
ops为空 | 不进入循环，minM = m，minN = n | 返回m * n（全矩阵都是 0，最大整数 0 出现 m*n 次） |
| 存在某个操作的 a 或 b 为 1 | 对应维度的最小值收敛为 1 | 交集退化为 1 行或 1 列，结果即 1×minN 或 minM×1 |
| 所有操作完全覆盖矩阵（a=m, b=n） | 最小值始终为 m、n | 返回m * n，所有格子值相同 |
复杂度分析
- 时间复杂度：O(k)，其中 k 为操作数（题目约束 k ≤ 10000）。只需一次线性扫描，不随矩阵面积增长。
- 空间复杂度：O(1)，仅使用两个整型变量，不分配与矩阵大小相关的任何空间。
对比之下，若用二维差分数组求解，仅差分数组本身就需要 O(m×n) 空间，在 m=n=40000 时根本无法分配；而本题的 O(k) 时间、O(1) 空间实现是完全意义上的最优解。
为什么朴素模拟不可行：一个直观反证
假设我们尝试用暴力法：为每个格子维护计数值，逐操作更新矩形区域内所有格子。最坏情况下，单次操作更新 m×n 个格子，k 次操作的总开销为 O(k·m·n)。当 m=n=40000、k=10000 时，运算量高达 1.6×10¹³ 量级，任何现代机器都无法在合理时间内完成——这正是题目设置超大矩阵边界的用意：逼迫解题者放弃模拟，去发现几何结构。
而矩形交集法的正确性根源在于：所有操作矩形共享左上角 (0,0)，交集矩形内的每个格子都被 k 次操作全部覆盖（值恒为 k），交集外的格子至少被某个操作漏掉（值 ≤ k-1）。于是"最大整数个数"与"所有矩形交集的面积"严格等价，一步到位。
仓库测试验证
仓库为本题提供了表驱动风格的单元测试，位于 598. Range Addition II_test.go：
package leetcode import ( "fmt" "testing" ) type question598 struct { para598 ans598 } // para 是参数 // one 代表第一个参数 type para598 struct { m int n int ops [][]int } // ans 是答案 // one 代表第一个答案 type ans598 struct { one int } func Test_Problem598(t *testing.T) { qs := []question598{ { para598{3, 3, [][]int{{2, 2}, {3, 3}}}, ans598{4}, }, } fmt.Printf("------------------------Leetcode Problem 598------------------------\n") for _, q := range qs { _, p := q.ans598, q.para598 fmt.Printf("【input】:%v 【output】:%v\n", p, maxCount(p.m, p.n, p.ops)) } fmt.Printf("\n\n\n") }测试用例直接对应题目官方示例：maxCount(3, 3, [[2,2],[3,3]])应返回4。测试采用para598/ans598成对结构组织输入输出，符合仓库统一的题解测试风格，可随时向qs追加新用例。
在仓库根目录运行以下命令即可验证（测试脚本定义见 gotest.sh）：
# 仅运行本题测试 go test -v -run Test_Problem598 ./leetcode/0598.Range-Addition-II/ # 生成全仓库覆盖率报告（本项目承诺 100% test coverage） go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...仓库基于 Go 1.19 构建，模块名为github.com/halfrost/LeetCode-Go（见 go.mod），leetcode/下每个题解目录均遵循"题目 + 源码 + 测试"三件套的布局规范。
总结
LeetCode 598「Range Addition II」是一道典型的"形式吓人、本质简单"的题目：
- 识别特征：所有更新矩形共享原点 (0,0)，是简化的关键；
- 核心结论：最大整数个数 = 所有操作矩形交集面积 =
min(a) × min(b)； - 实现代价：一次 O(k) 扫描 + 两个变量，O(1) 空间；
- 验证手段：仓库中的 实现源码 与 表驱动测试 可直接运行验证。
理解这道题的价值不仅在于 AC，更在于训练一种思维习惯：面对区间/矩形覆盖类问题时，先审视几何结构是否具备可简化的特殊性质（如公共锚点、单调性、全序性），再决定是否动用线段树、差分、扫描线等重型工具。当"每个矩形的起点都包含 [0,0]"这一性质被抓住时，一道看似困难的覆盖问题就化归为一行数学公式。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
