当前位置：首页 > news >正文

动态规划与二分查找解决LeetCode 363矩形区域最大和问题

news 2026/8/10 5:42:50

1. 问题背景与核心挑战

LeetCode 363题"矩形区域不超过K的最大数值和"是一个典型的二维矩阵处理问题，属于动态规划与搜索算法的结合应用。题目要求在一个给定的二维矩阵中，找到一个矩形区域，使得该区域内所有元素的和不超过给定的K值，同时这个和是所有可能矩形区域中最大的。

这个问题的难点在于：

矩阵尺寸可能很大（200x200量级），暴力枚举所有矩形区域时间复杂度高达O(n^4)
需要在满足sum<=K的条件下找到最大值，具有双重约束
二维数据的处理比一维情况复杂得多，需要考虑行列的双重维度

2. 解决方案的整体思路

2.1 二维前缀和预处理

二维前缀和是解决矩阵区域求和问题的关键技术。我们预先计算一个前缀和数组prefixSum，其中prefixSum[i][j]表示从矩阵左上角(0,0)到(i-1,j-1)位置的矩形区域和。

计算方式：

prefixSum = [[0]*(n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]

任意矩形区域(r1,c1)到(r2,c2)的和可以通过：

sum = prefixSum[r2+1][c2+1] - prefixSum[r1][c2+1] - prefixSum[r2+1][c1] + prefixSum[r1][c1]

在O(1)时间内得到。

2.2 枚举优化策略

直接枚举所有可能的矩形区域时间复杂度太高。我们可以采用固定上下边界，然后处理一维问题的策略：

枚举矩形的上边界row1（从0到m-1）
枚举矩形的下边界row2（从row1到m-1）
对于固定的row1和row2，计算每一列的和，转化为一维数组
在这个一维数组上寻找不超过K的最大子数组和

2.3 二分查找的应用

对于转化后的一维问题，我们需要找到子数组和不超过K的最大值。这时可以使用前缀和+二分查找的方法：

计算一维数组的前缀和S
对于每个j，我们需要找到最小的i，使得S[j] - S[i] <= K
这等价于找到S[i] >= S[j] - K的最小i
可以用TreeSet维护有序的前缀和，进行二分查找

3. 完整代码实现与解析

3.1 Python实现

import bisect def maxSumSubmatrix(matrix, k): if not matrix or not matrix[0]: return 0 m, n = len(matrix), len(matrix[0]) res = -float('inf') # 枚举左边界 for left in range(n): # 初始化行和数组 row_sums = [0] * m # 枚举右边界 for right in range(left, n): # 更新行和 for i in range(m): row_sums[i] += matrix[i][right] # 在一维数组上寻找不超过k的最大子数组和 prefix_sums = [0] cur_sum = 0 for num in row_sums: cur_sum += num # 找到第一个大于等于cur_sum - k的prefix_sum idx = bisect.bisect_left(prefix_sums, cur_sum - k) if idx < len(prefix_sums): res = max(res, cur_sum - prefix_sums[idx]) # 插入当前前缀和，保持有序 bisect.insort(prefix_sums, cur_sum) return res

3.2 关键点解析

行列枚举顺序：外层循环枚举列边界(left, right)，内层处理行。这样可以利用列数通常小于行数的特点（在LeetCode测试用例中），减少枚举次数。
TreeSet替代：Python中没有TreeSet，使用bisect模块维护有序列表来模拟。bisect.insort()相当于TreeSet的插入，bisect.bisect_left()相当于ceiling()操作。
边界处理：初始时prefix_sums包含0，处理子数组从第一个元素开始的情况。
性能优化：当发现res==k时可以直接返回，因为不可能有更大的满足条件的和。