LeetCode 598 区间加法 II：从暴力模拟到数学最优解，掌握区间覆盖问题核心

在算法刷题和面试准备中LeetCode 上的“区间加法 II”是一道看似简单实则能有效考察对问题本质理解和优化思维的经典题目。很多同学初次接触时可能会不假思索地选择模拟整个操作过程结果在较大的数据规模下遭遇超时。本文将带你深入剖析力扣第 598 题从最直观的暴力解法入手逐步推导出最优的数学解法并用 Python 实现。无论你是正在入门算法的新手还是希望巩固优化思路的进阶开发者都能通过本文掌握“降维打击”的解题技巧提升解决同类区间覆盖问题的能力。1. 背景与核心概念在开始解题之前我们首先要明确题目到底在问什么以及它背后考察的核心算法思想是什么。1.1 问题描述与场景还原力扣 598. 区间加法 II的官方描述如下给定一个初始元素全部为0大小为m x n的二维矩阵M。同时给你一系列操作ops其中每个操作用一个包含两个正整数a和b的数组表示含义是对矩阵M中所有满足0 i a且0 j b的元素M[i][j]进行加一操作。你需要执行完所有操作后返回矩阵中最大整数的个数。通俗解释想象你有一张m行n列的方格纸一开始所有格子都是0。现在你得到一系列指令ops每个指令告诉你“请把左上角区域即前a行、前b列这个矩形范围内的所有格子都加上1”。你需要执行所有指令最后看看整张纸上最大的数字是多少并且数一数有多少个格子是这个最大数字。示例 1输入: m 3, n 3, ops [[2,2], [3,3]] 输出: 4 解释: 初始矩阵 M [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 执行操作 [2,2] 后M [[1, 1, 0], [1, 1, 0], [0, 0, 0]] 执行操作 [3,3] 后M [[2, 2, 1], [2, 2, 1], [1, 1, 1]] 最大整数是 2共有 4 个值为 2 的元素。因此返回 4。1.2 核心考察点与常见误区这道题被标记为“简单”但其真正的价值在于引导我们思考如何避免不必要的计算。它主要考察以下几个点问题抽象能力能否将二维矩阵的多次区间加操作抽象为一个更简单的数学问题。优化思维当m,n和操作次数可能很大时例如达到10^4量级模拟每一步加法时间复杂度 O(k * m * n)是完全不可行的。必须寻找规律。边界条件处理当操作列表ops为空时应该如何处理常见的误区就是陷入“模拟”的思维定式试图真的去构建这个矩阵并执行所有加法操作。这不仅效率低下也错过了题目设计的精妙之处。2. 环境准备与思路分析在动手写代码之前我们先搭建好解题环境并梳理从暴力解到最优解的思考路径。2.1 解题环境准备对于 LeetCode 刷题一个简洁高效的本地环境能极大提升练习和调试效率。编程语言Python 3.8。本文所有代码均基于 Python 3。开发工具任选其一即可。本地IDEPyCharm, VSCode。建议安装 Python 插件配置好代码提示和调试功能。在线平台力扣LeetCode官网的代码编辑器已足够完成本题。核心思路验证我们可以在本地创建测试用例来验证算法的正确性而无需依赖在线判题系统。一个简单的本地测试脚本结构如下# test_leetcode598.py def maxCount(m, n, ops): # 这里是你的解法函数 pass if __name__ __main__: # 测试用例1 m, n 3, 3 ops [[2,2], [3,3]] print(f测试1: m{m}, n{n}, ops{ops}) print(f预期输出: 4) print(f实际输出: {maxCount(m, n, ops)}) print(- * 20) # 测试用例2: ops为空 m, n 3, 3 ops [] print(f测试2: m{m}, n{n}, ops{ops}) print(f预期输出: 9) # 所有元素都是0最大整数0的个数是9 print(f实际输出: {maxCount(m, n, ops)})2.2 从暴力解到数学解的思维推导第一步最直观的暴力解法不可行但有助于理解暴力法的思路是严格按照题目描述模拟初始化一个m x n的全零矩阵。遍历ops中的每一个操作[a, b]。对于每个操作使用两层循环遍历i从0到a-1j从0到b-1对矩阵对应位置加一。遍历整个矩阵找到最大值并统计其出现次数。def maxCount_bruteforce(m: int, n: int, ops: List[List[int]]) - int: # 注意此方法在 m, n, k 较大时会超时仅用于理解 import itertools # 初始化矩阵 matrix [[0] * n for _ in range(m)] # 执行所有操作 for a, b in ops: for i in range(a): for j in range(b): matrix[i][j] 1 # 找到最大值并计数 max_val 0 count 0 for row in matrix: for val in row: if val max_val: max_val val count 1 elif val max_val: count 1 return count时间复杂度分析假设有k个操作每个操作平均影响(a*b)个元素最坏情况下每次操作都覆盖接近整个矩阵则总操作次数约为O(k * m * n)。当m, n, k达到10^4时运算量是10^12级别必然超时。第二步观察规律寻找突破口既然暴力法行不通我们必须观察规律。回顾示例操作[2,2]影响了第0、1行第0、1列。操作[3,3]影响了第0、1、2行第0、1、2列。最终哪些格子被加了两次只有那些同时被所有操作覆盖的格子即行索引在所有操作的a的最小值以内且列索引在所有操作的b的最小值以内的格子。核心洞察每次操作都是对矩阵左上角的一个矩形区域进行加一。一个格子最终的值等于覆盖了这个格子的操作的数量。因此值最大的格子就是被所有操作都覆盖了的格子。被所有操作覆盖的格子其行索引必须小于所有a中的最小值min_a列索引必须小于所有b中的最小值min_b。这些格子的数量就是min_a * min_b。特别地如果操作列表ops为空那么没有任何操作执行所有格子保持为0最大整数0的个数就是整个矩阵的大小m * n。第三步得出最优解问题瞬间简化我们不需要矩阵只需要遍历一次ops数组找到所有a的最小值和所有b的最小值。最终答案就是min_a * min_b同时需要与m和n取较小值因为操作可能给出比矩阵本身更大的范围例如a m但实际有效的格子不能超出矩阵边界。3. 核心算法实现与代码详解掌握了数学原理后我们来实现最优解并详细分析代码的每一个部分。3.1 最优解 Python 实现from typing import List class Solution: def maxCount(self, m: int, n: int, ops: List[List[int]]) - int: 计算执行所有区间加法操作后矩阵中最大整数的个数。 参数: m (int): 矩阵行数 n (int): 矩阵列数 ops (List[List[int]]): 操作列表每个操作是[a, b] 返回: int: 最大整数的个数 # 初始化最小行和最小列为矩阵的原始边界 min_row m min_col n # 遍历所有操作更新被所有操作共同覆盖区域的行列边界 for a, b in ops: # 取当前操作范围与历史最小范围的交集 min_row min(min_row, a) min_col min(min_col, b) # 共同覆盖区域的格子数即为最大整数的个数 return min_row * min_col代码行数非常精简核心逻辑只有 4 行。3.2 代码逐行解析与边界处理初始化 (min_row m,min_col n)为什么初始化为m和n因为矩阵的有效索引范围是[0, m-1]和[0, n-1]。任何操作的有效a和b都不可能大于m和n大于的部分不影响矩阵。初始化为m和n可以保证在遍历ops时min函数能正确取到实际有效的最小值。更重要的是它完美处理了ops为空的情况遍历不会执行min_row和min_col保持为m和n最终返回m * n这正是全为0的矩阵中最大数0的个数。遍历操作 (for a, b in ops:)使用 Python 的迭代解包直接获取每个操作的a和b。更新最小范围 (min_row min(min_row, a),min_col min(min_col, b))这是算法的核心。min_row记录了所有操作中a的最小值即所有操作都覆盖的最大行索引1。min_col同理。这个交集矩形就是被所有操作“雨露均沾”的区域。返回结果 (return min_row * min_col)交集矩形的面积即为被加次数最多的格子数量也就是最大整数的个数。3.3 复杂度分析时间复杂度O(k)其中k是操作列表ops的长度。我们只需要一次线性遍历。空间复杂度O(1)只使用了常数级别的额外变量 (min_row,min_col)。与暴力法的 O(m*n) 空间相比有巨大优势。4. 完整测试与验证案例理论需要实践检验。下面我们构建多个测试案例包括常规情况、边界情况和特殊输入来验证算法的鲁棒性。4.1 基础功能测试我们将上面的解法嵌入一个完整的测试框架中。# leetcode598_solution.py from typing import List class Solution: def maxCount(self, m: int, n: int, ops: List[List[int]]) - int: min_row, min_col m, n for a, b in ops: min_row min(min_row, a) min_col min(min_col, b) return min_row * min_col def test(): solution Solution() # 测试用例1: 题目示例 assert solution.maxCount(3, 3, [[2,2], [3,3]]) 4 print(测试用例1通过: m3, n3, ops[[2,2],[3,3]] - 4) # 测试用例2: 单个操作 assert solution.maxCount(3, 3, [[1,1]]) 1 print(测试用例2通过: m3, n3, ops[[1,1]] - 1) # 测试用例3: 操作范围超出矩阵 assert solution.maxCount(2, 2, [[5,5], [3,2]]) 4 # min(5,3,2)2, min(5,2,2)2, 2*24 print(测试用例3通过: m2, n2, ops[[5,5],[3,2]] - 4) # 测试用例4: 无操作 assert solution.maxCount(40000, 40000, []) 40000 * 40000 print(测试用例4通过: m40000, n40000, ops[] - 1600000000) # 测试用例5: 操作a或b为0 (根据题目描述a和b为正整数但为防御考虑) # 假设输入保证为正整数此用例仅作思维扩展。若a或b为0则该操作不影响任何元素。 # 在算法中min_row或min_col可能被更新为0最终结果为0。 # assert solution.maxCount(3, 3, [[2,2], [0,3]]) 0 # 假设允许0输入 # print(测试用例5通过假设性) # 测试用例6: 大量操作性能测试模拟 import random, time m, n 40000, 40000 k 10000 # 生成随机操作a和b在[1, 40000]之间 random_ops [[random.randint(1, m), random.randint(1, n)] for _ in range(k)] start time.time() result solution.maxCount(m, n, random_ops) end time.time() print(f测试用例6通过: 大规模数据 m{m}, n{n}, k{k}, 结果{result}, 耗时 {end-start:.4f} 秒) print(所有基础测试用例通过) if __name__ __main__: test()运行上述脚本你将看到所有测试用例快速通过尤其是用例6即使面对40000*40000的矩阵规模和10000次操作也能在毫秒级完成计算充分体现了 O(k) 算法的效率。4.2 与暴力法的结果对比验证为了确保我们的优化算法结果正确可以编写一个函数在小规模数据上对比暴力解与最优解的结果。def compare_with_bruteforce(m, n, ops): 在小规模数据上对比最优解和暴力解用于验证正确性 def brute_force(m, n, ops): matrix [[0] * n for _ in range(m)] for a, b in ops: for i in range(a): for j in range(b): if i m and j n: # 防止索引越界 matrix[i][j] 1 max_val 0 count 0 for row in matrix: for val in row: if val max_val: max_val val count 1 elif val max_val: count 1 return count sol Solution() optimal_result sol.maxCount(m, n, ops) brute_result brute_force(m, n, ops) if optimal_result brute_result: print(f验证通过: m{m}, n{n}, ops{ops}) print(f 最优解: {optimal_result}, 暴力解: {brute_result}) else: print(f验证失败: m{m}, n{n}, ops{ops}) print(f 最优解: {optimal_result}, 暴力解: {brute_result}) return optimal_result brute_result # 运行一些对比测试 test_cases [ (3, 3, [[2,2], [3,3]]), (5, 5, [[1,5], [5,1], [3,3]]), (2, 2, [[5,5]]), (4, 4, []), ] all_pass all(compare_with_bruteforce(*case) for case in test_cases) print(f\n所有对比测试 {全部通过 if all_pass else 存在失败})这个对比验证能给你充分的信心证明数学优化解法的正确性。5. 算法扩展与变式思考掌握了基础解法后我们可以思考一些相关的变式问题这有助于深化对区间操作类问题的理解。5.1 如果操作不是加一而是加一个任意值val呢原题是每次加一。如果操作变为[a, b, val]表示对左上角a x b区域加valval可为正或负。求最终矩阵的最大值及其个数。思路分析 此时一个格子最终的值等于所有覆盖它的操作的val之和。最大值出现的区域仍然是所有val为正数的操作共同覆盖的区域吗不一定因为负数的val会减少值。问题变得复杂更像是一个二维差分或二维前缀和的问题。解决方法二维差分这是处理此类“区间批量增加一个值”的高效方法。遍历所有操作在差分数组上进行标记。最后通过计算前缀和得到原矩阵。再遍历矩阵找最大值和计数。def maxCount_with_values(m: int, n: int, ops: List[List[int]]) - (int, int): 变式ops中的每个元素是 [a, b, val] 返回最大值最大值的个数 # 初始化差分数组多一圈方便处理边界 diff [[0] * (n 2) for _ in range(m 2)] for a, b, val in ops: if a m: a m if b n: b n # 二维差分更新公式对左上角(0,0)到右下角(a-1, b-1)的矩形加val diff[1][1] val diff[1][b1] - val diff[a1][1] - val diff[a1][b1] val # 计算前缀和得到原矩阵 matrix [[0] * n for _ in range(m)] max_val float(-inf) count 0 # 利用差分数组恢复原矩阵并找最大值 for i in range(1, m1): for j in range(1, n1): # 计算前缀和 diff[i][j] diff[i-1][j] diff[i][j-1] - diff[i-1][j-1] current_val diff[i][j] if current_val max_val: max_val current_val count 1 elif current_val max_val: count 1 return max_val, count复杂度时间复杂度 O(mn k)空间复杂度 O(mn)。当 m, n 很大时可能仍需优化但比模拟每个操作要高效得多。5.2 如果操作不是针对左上角而是任意矩形区域呢原题操作区域总是从(0,0)开始。如果操作定义为对任意矩形区域[x1, y1, x2, y2]加一求最大整数的个数。思路分析 这变成了一个标准的**二维区间更新、单点查询或最终统一查询**问题。二维差分依然是标准解法。最终最大值的个数需要在得到整个矩阵后遍历寻找。5.3 在数据库或实际业务中的类比这种“区间叠加求最大覆盖”的思想在现实中有很多应用用户权限系统多个角色对某个功能模块的权限进行叠加例如可读、可写最终用户的权限是这些角色的并集或最高级别。寻找拥有“最高权限”的用户群可以类比为寻找被所有高权限角色覆盖的用户。广告投放统计在多个时间段、多个地域投放广告统计曝光量最大的时段和地域组合。资源调度多个任务请求占用某个资源池的不同子区域寻找负载最重的区域。理解这类问题的抽象模型能帮助你在遇到实际业务问题时快速识别并套用合适的算法。6. 常见错误与排查指南即使在理解了最优解法后实现时也可能遇到一些陷阱。下面列出常见错误及其解决方法。问题现象可能原因解决方案与排查思路返回结果比预期小未正确处理ops为空的情况。当ops为空时应返回m * n。检查代码逻辑。最优解法中将min_row和min_col初始化为m和n遍历为空时直接返回m*n这是正确的。如果初始化为float(inf)则需要在遍历后判断是否被更新过。返回结果比预期大操作中的a或b可能大于m或n。在计算最小范围时误用了max函数。题目保证a和b是正整数但未明确说明与m, n的关系。我们的算法中min_row min(min_row, a)是合理的因为a若大于m其有效部分也只是前m行取min会自动将其限制到m。确保你使用的是min而不是max。代码在 LeetCode 上报语法错误Python 版本或函数签名问题。LeetCode 使用List需要从typing导入。在代码开头添加from typing import List。确保函数名、参数名与题目要求一致本题是def maxCount(self, m: int, n: int, ops: List[List[int]]) - int:。本地测试通过提交超时可能错误地使用了暴力解法或者最优解法中存在低效操作如在循环中进行了不必要的列表创建。确认你的算法时间复杂度是O(k)并且没有在循环内嵌套其他循环或调用高复杂度函数。使用我们提供的最优解代码。对于变式问题如加任意值结果错误二维差分的构建或前缀和计算公式错误。仔细推导二维差分公式。记住核心四步更新diff[x1][y1] valdiff[x1][y21] - valdiff[x21][y1] - valdiff[x21][y21] val其中(x1,y1)是左上角(x2,y2)是右下角。恢复原矩阵时prefix[i][j] diff[i][j] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1]调试建议使用小数据测试用题目示例和自定义的简单案例如m2,n2在本地或力扣的 Playground 运行打印中间变量。可视化对于二维矩阵问题可以尝试手动画一个 3x3 或 4x4 的网格模拟操作过程验证你的算法得出的“交集矩形”是否正确。边界测试务必测试ops[]ops中包含a0或b0如果允许am,bn等情况。7. 最佳实践与刷题心得解决这道题的过程是一个典型的算法优化案例。从中我们可以总结出适用于 LeetCode 乃至实际工程问题解决的最佳实践。7.1 算法优化思维模式从暴力法开始思考不要害怕先想出最直观、可能低效的解法。这是理解问题的第一步也是寻找优化线索的基础。寻找规律与不变性在暴力模拟的过程中主动观察数据的变化规律。本题的关键规律是“最大值的区域是所有操作范围的交集”。很多题目都隐藏着类似的“不变量”或“单调性”。降维打击当数据规模很大时思考能否将问题转化到更低的维度或更简单的模型。本题将二维的矩阵加操作转化为了对一维边界a和b求最小值。考虑极端情况空操作 (ops[])、单个操作、操作范围极大等情况往往是代码的“死角”也是面试官喜欢考察的点。7.2 Python 编码实践善用内置函数和迭代本题中for a, b in ops:和min()函数的使用让代码非常简洁。Python 的迭代器和解包能提升代码可读性。类型提示虽然 LeetCode 不强制但在本地代码或大型项目中使用from typing import List, Tuple等类型提示有助于提高代码可维护性和 IDE 的智能提示。函数单一职责将解题函数maxCount保持简洁只负责核心逻辑。测试、验证等辅助功能放在其他函数或if __name__ __main__:块中。7.3 针对区间操作类问题的通用策略“区间加法 II”属于“区间更新”问题家族。遇到类似问题可以按以下策略思考区间是否固定起点如本题从(0,0)开始可能用找交集的方法。如果是任意区间优先考虑差分数组一维/二维。是否需要动态查询如果需要在多次更新的过程中间查询某个值可能需要更复杂的数据结构如线段树或树状数组。操作是否可交换本题的加法操作是可交换和可结合的顺序不影响最终结果。如果操作不可交换如先乘后加则需要记录操作顺序或使用不同的方法。数据范围始终根据m,n,k的数据范围估算暴力法的复杂度并判断是否需要O(log N)或O(1)的优化方法。7.4 在面试中如何阐述解题思路如果你在面试中遇到此题可以按照以下结构来沟通澄清问题复述题目确认输入输出和边界条件如ops为空。提出暴力法先给出最直接的模拟思路并分析其时间复杂度 O(kmn) 和空间复杂度 O(m*n)指出在大数据下不可行。寻找优化阐述你观察到的规律——“每次操作都是左上角矩形”、“一个格子最终值等于覆盖它的操作数”、“因此最大值出现在所有操作的交集矩形中”。给出最优解将问题转化为求所有a的最小值和所有b的最小值答案为min_a * min_b。强调时间复杂度 O(k)空间复杂度 O(1)。代码实现写出简洁的代码。测试用例主动提出测试用例包括常规示例、空操作、单操作、大范围操作等。扩展讨论如果时间允许可以简要提一下如果操作值不同或区间任意时的差分数组解法展示知识广度。通过“区间加法 II”这道题我们不仅学会了一个巧妙的优化技巧更重要的是训练了从具体操作中抽象出数学本质的思维能力。这种能力在解决更复杂的算法问题时至关重要。建议读者在理解本题后可以去尝试 LeetCode 上其他区间相关题目如 370. 区间加法一维差分、1094. 拼车一维差分应用、731. 我的日程安排 II差分思想等巩固和深化对这一类问题的掌握。