线性动态规划：最大子矩阵和（Maximum Submatrix Sum）的变种——子矩阵和不超过阈值的最大子矩阵面积
字数 3652 2025-12-20 18:38:00

线性动态规划：最大子矩阵和（Maximum Submatrix Sum）的变种——子矩阵和不超过阈值的最大子矩阵面积

题目描述

给你一个 \(m \times n\) 的整数矩阵 matrix 和一个整数 threshold。
你需要找到一个子矩阵，使得这个子矩阵内所有元素的和不超过 threshold，并且这个子矩阵的面积尽可能大。
子矩阵 定义为矩阵中一个连续的矩形区域（至少包含一个元素）。
你需要返回满足条件的最大子矩阵的面积（即行数 × 列数）。
如果不存在这样的子矩阵，则返回 0。

示例：
输入：

matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
threshold = 2

输出：4
解释：
子矩阵

[1, 0]
[0, -2]

的和为 1+0+0+(-2) = -1 ≤ 2，面积是 2×2=4，没有更大的满足条件的子矩阵。

解题过程

第一步：将二维问题压缩为一维问题

一个子矩阵由上下边界（行范围）和左右边界（列范围）确定。
我们可以枚举上下边界（第 top 行到第 bottom 行），然后把中间每一列的元素压缩成一个一维数组：

  • 对于每一列 j，计算从第 top 行到第 bottom 行的和，记为 colSum[j]。
    这样，原问题就变成了：
    给定一个一维数组 colSum，找一个子数组，使得子数组的和不超过 threshold，并且子数组的长度尽可能大。

第二步：一维子问题——和不超过阈值的最大长度子数组

问题：给定数组 arr 和阈值 T，求最长的子数组，其和 ≤ T。

暴力法（不可行）：

枚举所有子数组，计算和，判断是否 ≤ T。复杂度 \(O(n^2)\)，放在二维中会变成 \(O(m^2 n^2)\)，太大。

高效方法：

我们可以在 \(O(n)\) 内用滑动窗口或前缀和+二分查找解决。

  • 计算前缀和 prefix[0] = 0, prefix[i] = arr[0] + arr[1] + ... + arr[i-1]。
  • 对于每个右端点 r，我们想找最小的左端点 l，使得：

\[prefix[r+1] - prefix[l] \leq T \]

即：

\[prefix[l] \geq prefix[r+1] - T \]

  • 由于我们固定 r，prefix[r+1] - T 是固定的，我们需要在 l ≤ r 中找最小的满足上述条件的 l，这样窗口长度 r-l+1 最大。
  • 我们可以用有序集合（比如 Python 的 SortedList 或 C++ 的 multiset）维护已经见过的前缀和，然后每次用二分查找找到最小的满足条件的 l。

复杂度：对于每个 r，二分查找 O(log n)，总共 O(n log n)。
注意：在本题中，列数 n 最多可能几百，O(n log n) 是可行的。

第三步：整体算法框架

  1. 枚举上边界 top 从 0 到 m-1。
  2. 初始化一个数组 colSum 长度为 n，初始全 0。
  3. 枚举下边界 bottom 从 top 到 m-1：
    • 将第 bottom 行的每个元素加到 colSum 对应列上（即更新列的前缀和）。
    • 此时 colSum 就表示从 top 到 bottom 行的列和数组。
    • 在 colSum 上求解一维问题：和不超过 threshold 的最大长度子数组的长度 len。
    • 面积 = (bottom - top + 1) * len，更新最大面积。
  4. 返回最大面积。

时间复杂度：

  • 枚举上下边界 O(m²)，每次处理一维问题 O(n log n)，总 O(m² n log n)。
  • 在 m、n ≤ 200 时可行。

第四步：一维问题的实现细节（前缀和+有序集合）

我们需要长度最大的子数组，其和 ≤ threshold。
设当前列和数组为 arr[0..n-1]。

  • 记 prefix[j] = arr[0] + arr[1] + ... + arr[j-1]，prefix[0] = 0。
  • 子数组 arr[l..r] 的和 = prefix[r+1] - prefix[l]。
    条件：prefix[r+1] - prefix[l] ≤ threshold ⇒ prefix[l] ≥ prefix[r+1] - threshold。

我们遍历右端点 r（0 到 n-1），并维护一个有序列表 sorted_prefix 存放已经遍历过的前缀和（即 prefix[0], prefix[1], ..., prefix[r]）。

  • 对于当前 prefix[r+1]，计算 target = prefix[r+1] - threshold。
  • 在 sorted_prefix 中二分查找第一个 ≥ target 的值，其对应的下标就是最小的左端点 l，子数组长度为 r - l + 1。
  • 更新最大长度。
  • 然后将 prefix[r+1] 加入有序列表。

注意：因为 l 可以等于 r+1 吗？不行，因为子数组至少一个元素，所以左端点 ≤ 右端点。但在前缀和数组中，l 对应 prefix[l]，r 对应 prefix[r+1]，我们要保证 l ≤ r，即我们只在已遍历过的前缀和中查找（不包括当前 prefix[r+1]）。
所以顺序是：

  • 计算 target 并用当前有序列表查找。
  • 插入 prefix[r+1] 到有序列表。

第五步：例子推演

矩阵：

[1, 0, 1]
[0,-2, 3]

threshold = 2。

枚举 top=0：

  • bottom=0：
    colSum = [1, 0, 1]
    一维：找和 ≤2 的最长子数组长度。
    arr=[1,0,1]，前缀和=[0,1,1,2]。
    r=0: target=1-2=-1，找≥-1的最小前缀是 prefix[0]=0，l=0，长度=1。
    r=1: target=1-2=-1，找≥-1的最小前缀是 prefix[0]=0，长度=2。
    r=2: target=2-2=0，找≥0的最小前缀是 prefix[0]=0，长度=3。
    最大长度=3，面积=1×3=3。

  • bottom=1：
    colSum 加上第二行 = [1+0, 0+(-2), 1+3] = [1, -2, 4]。
    arr=[1,-2,4]，前缀和=[0,1,-1,3]。
    r=0: target=1-2=-1，最小前缀≥-1 是 prefix[0]=0，长度=1。
    r=1: target=-1-2=-3，最小前缀≥-3 是 prefix[0]=0，长度=2。
    r=2: target=3-2=1，最小前缀≥1 是 prefix[1]=1，l=1，长度=2-1+1=2? 检查：左端点 l=1 对应原数组下标1到2的和= arr[1]+arr[2] = (-2)+4=2 ≤ threshold，长度=2。
    最大长度=2，面积=2×2=4。

枚举 top=1：

  • bottom=1：
    colSum=[0,-2,3]。
    arr=[0,-2,3]，前缀和=[0,0,-2,1]。
    r=0: target=0-2=-2，最小前缀≥-2 是 prefix[0]=0，长度=1。
    r=1: target=-2-2=-4，最小前缀≥-4 是 prefix[0]=0，长度=2。
    r=2: target=1-2=-1，最小前缀≥-1 是 prefix[0]=0，长度=3。
    最大长度=3，面积=1×3=3。

比较所有面积：最大为 4。

第六步：边界情况

  • 矩阵全是负数且 threshold 是负数：可能没有子矩阵和 ≤ threshold（因为和可能比 threshold 更小才行）。但我们的算法仍然会找到最接近的，如果找不到则返回 0，但注意：即使全负，只要有一个元素的值 ≤ threshold，面积至少是 1。
  • 如果整个矩阵的和 ≤ threshold，则最大面积是 m×n。

第七步：复杂度总结

  • 枚举上下边界 O(m²)
  • 一维问题 O(n log n)
  • 总 O(m² n log n)，适合 m、n 在 200 左右的规模。

如果你希望进一步优化，一维问题可以用双指针滑动窗口吗？
可以，但要求数组元素全为正数，因为全正时增大左端点 l 会减少和，从而可能满足 ≤ threshold，但数组可能有负数，所以滑动窗口不一定单调，不能用双指针。
所以用前缀和+有序集合是最通用的。

这道题是最大子矩阵和的一个经典变种，将矩阵压缩为一维，再通过前缀和与二分查找解决一维约束问题，是处理“不超过某阈值的最长子数组”的典型方法。

线性动态规划：最大子矩阵和（Maximum Submatrix Sum）的变种——子矩阵和不超过阈值的最大子矩阵面积 题目描述 给你一个 \( m \times n \) 的整数矩阵 matrix 和一个整数 threshold 。 你需要找到一个 子矩阵 ，使得这个子矩阵内所有元素的和 不超过 threshold ，并且这个子矩阵的 面积 尽可能大。 子矩阵 定义为矩阵中一个连续的矩形区域（至少包含一个元素）。 你需要返回满足条件的最大子矩阵的面积（即行数 × 列数）。 如果不存在这样的子矩阵，则返回 0。 示例 ： 输入： 输出： 4 解释： 子矩阵 的和为 1+0+0+(-2) = -1 ≤ 2，面积是 2×2=4，没有更大的满足条件的子矩阵。 解题过程 第一步：将二维问题压缩为一维问题 一个子矩阵由 上下边界 （行范围）和 左右边界 （列范围）确定。 我们可以枚举 上下边界 （第 top 行到第 bottom 行），然后把中间每一列的元素压缩成一个一维数组： 对于每一列 j ，计算从第 top 行到第 bottom 行的和，记为 colSum[j] 。 这样，原问题就变成了： 给定一个一维数组 colSum ，找一个子数组，使得子数组的和不超过 threshold ，并且子数组的长度尽可能大。 第二步：一维子问题——和不超过阈值的最大长度子数组 问题：给定数组 arr 和阈值 T ，求最长的子数组，其和 ≤ T。 暴力法 （不可行）： 枚举所有子数组，计算和，判断是否 ≤ T。复杂度 \(O(n^2)\)，放在二维中会变成 \(O(m^2 n^2)\)，太大。 高效方法 ： 我们可以在 \(O(n)\) 内用 滑动窗口 或 前缀和+二分查找 解决。 计算前缀和 prefix[0] = 0 , prefix[i] = arr[0] + arr[1] + ... + arr[i-1] 。 对于每个右端点 r ，我们想找最小的左端点 l ，使得： \[ prefix[ r+1] - prefix[ l ] \leq T \] 即： \[ prefix[ l] \geq prefix[ r+1 ] - T \] 由于我们固定 r ， prefix[r+1] - T 是固定的，我们需要在 l ≤ r 中找 最小的满足上述条件的 l ，这样窗口长度 r-l+1 最大。 我们可以用 有序集合 （比如 Python 的 SortedList 或 C++ 的 multiset ）维护已经见过的前缀和，然后每次用二分查找找到最小的满足条件的 l 。 复杂度 ：对于每个 r ，二分查找 O(log n)，总共 O(n log n)。 注意 ：在本题中，列数 n 最多可能几百，O(n log n) 是可行的。 第三步：整体算法框架 枚举上边界 top 从 0 到 m-1。 初始化一个数组 colSum 长度为 n，初始全 0。 枚举下边界 bottom 从 top 到 m-1： 将第 bottom 行的每个元素加到 colSum 对应列上（即更新列的前缀和）。 此时 colSum 就表示从 top 到 bottom 行的列和数组。 在 colSum 上求解一维问题：和不超过 threshold 的最大长度子数组的长度 len 。 面积 = (bottom - top + 1) * len ，更新最大面积。 返回最大面积。 时间复杂度 ： 枚举上下边界 O(m²)，每次处理一维问题 O(n log n)，总 O(m² n log n)。 在 m、n ≤ 200 时可行。 第四步：一维问题的实现细节（前缀和+有序集合） 我们需要 长度最大 的子数组，其和 ≤ threshold。 设当前列和数组为 arr[0..n-1] 。 记 prefix[j] = arr[0] + arr[1] + ... + arr[j-1] ， prefix[0] = 0 。 子数组 arr[l..r] 的和 = prefix[r+1] - prefix[l] 。 条件： prefix[r+1] - prefix[l] ≤ threshold ⇒ prefix[l] ≥ prefix[r+1] - threshold 。 我们遍历右端点 r （0 到 n-1），并维护一个有序列表 sorted_prefix 存放已经遍历过的前缀和（即 prefix[0] , prefix[1] , ..., prefix[r] ）。 对于当前 prefix[r+1] ，计算 target = prefix[r+1] - threshold 。 在 sorted_prefix 中二分查找第一个 ≥ target 的值，其对应的下标就是最小的左端点 l ，子数组长度为 r - l + 1 。 更新最大长度。 然后将 prefix[r+1] 加入有序列表。 注意 ：因为 l 可以等于 r+1 吗？不行，因为子数组至少一个元素，所以左端点 ≤ 右端点。但在前缀和数组中， l 对应 prefix[l] ， r 对应 prefix[r+1] ，我们要保证 l ≤ r ，即我们只在已遍历过的前缀和中查找（不包括当前 prefix[r+1] ）。 所以顺序是： 计算 target 并用当前有序列表查找。 插入 prefix[r+1] 到有序列表。 第五步：例子推演 矩阵： threshold = 2。 枚举 top=0： bottom=0： colSum = [ 1, 0, 1 ] 一维：找和 ≤2 的最长子数组长度。 arr=[ 1,0,1]，前缀和=[ 0,1,1,2 ]。 r=0: target=1-2=-1，找≥-1的最小前缀是 prefix[ 0 ]=0，l=0，长度=1。 r=1: target=1-2=-1，找≥-1的最小前缀是 prefix[ 0 ]=0，长度=2。 r=2: target=2-2=0，找≥0的最小前缀是 prefix[ 0 ]=0，长度=3。 最大长度=3，面积=1×3=3。 bottom=1： colSum 加上第二行 = [ 1+0, 0+(-2), 1+3] = [ 1, -2, 4 ]。 arr=[ 1,-2,4]，前缀和=[ 0,1,-1,3 ]。 r=0: target=1-2=-1，最小前缀≥-1 是 prefix[ 0 ]=0，长度=1。 r=1: target=-1-2=-3，最小前缀≥-3 是 prefix[ 0 ]=0，长度=2。 r=2: target=3-2=1，最小前缀≥1 是 prefix[ 1]=1，l=1，长度=2-1+1=2? 检查：左端点 l=1 对应原数组下标1到2的和= arr[ 1]+arr[ 2 ] = (-2)+4=2 ≤ threshold，长度=2。 最大长度=2，面积=2×2=4。 枚举 top=1： bottom=1： colSum=[ 0,-2,3 ]。 arr=[ 0,-2,3]，前缀和=[ 0,0,-2,1 ]。 r=0: target=0-2=-2，最小前缀≥-2 是 prefix[ 0 ]=0，长度=1。 r=1: target=-2-2=-4，最小前缀≥-4 是 prefix[ 0 ]=0，长度=2。 r=2: target=1-2=-1，最小前缀≥-1 是 prefix[ 0 ]=0，长度=3。 最大长度=3，面积=1×3=3。 比较所有面积：最大为 4。 第六步：边界情况 矩阵全是负数且 threshold 是负数：可能没有子矩阵和 ≤ threshold（因为和可能比 threshold 更小才行）。但我们的算法仍然会找到最接近的，如果找不到则返回 0，但注意：即使全负，只要有一个元素的值 ≤ threshold，面积至少是 1。 如果整个矩阵的和 ≤ threshold，则最大面积是 m×n。 第七步：复杂度总结 枚举上下边界 O(m²) 一维问题 O(n log n) 总 O(m² n log n)，适合 m、n 在 200 左右的规模。 如果你希望进一步优化，一维问题可以用 双指针滑动窗口 吗？ 可以，但要求数组元素全为正数，因为全正时增大左端点 l 会减少和，从而可能满足 ≤ threshold，但数组可能有负数，所以滑动窗口不一定单调，不能用双指针。 所以用前缀和+有序集合是最通用的。 这道题是 最大子矩阵和 的一个经典变种，将矩阵压缩为一维，再通过前缀和与二分查找解决一维约束问题，是处理“不超过某阈值的最长子数组”的典型方法。