矩形区域不超过 K 的最大数值和

难度: Hard

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

示例 1：

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例 2：

输入：matrix = [[2,2,-1]], k = 3
输出：3

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-10⁵ <= k <= 10⁵

进阶：如果行数远大于列数，该如何设计解决方案？

Submission

运行时间: 520 ms

内存: 16.9 MB

# class Solution:
#     def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
#         n , m = len(matrix) , len(matrix[0])
#         mt = [[0] * m for _ in range(n)]
#         mt[0][0] = matrix[0][0]
#         for i in range(n):
#             for j in range(m):
#                 if i == 0 and j == 0:
#                     continue
#                 if i == 0 and j != 0:
#                     mt[i][j] = mt[i][j-1] + matrix[i][j]
#                     continue
#                 if j == 0 and i != 0:
#                     mt[i][j] = mt[i-1][j] + matrix[i][j]
#                     continue
#                 mt[i][j] = mt[i-1][j] + mt[i][j-1] - mt[i-1][j-1] + matrix[i][j]
#         return mt
import bisect
class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        m = len(matrix)
        Row, Col = len(matrix), len(matrix[0])
        res = float("-inf")
        for ru in range(Row):
            col_sum = [0 for _ in range(Col)]
            for rd in range(ru, Row):
                for c in range(Col):
                    if matrix[rd][c] == k:
                        return k
                    col_sum[c] += matrix[rd][c]
                presum = [0]
                cur_sum = 0
                for colsum in col_sum:
                    cur_sum += colsum
                    idx = bisect.bisect_left(presum, cur_sum - k)
                    if idx < len(presum):
                        res = max(res, cur_sum - presum[idx])
                        if res == k:
                            return k
                    bisect.insort(presum, cur_sum)
        return res

Explain

此题解采用了前缀和加二分查找的方法来解决问题。首先，我们遍历所有可能的上下边界组合，然后计算这个边界内每一列的和，并将其保存在col_sum数组中。接着，我们利用前缀和的概念来计算从第一列到当前列的所有元素的和，存储在cur_sum中。为了找到一个子矩阵的和不超过k，我们需要在presum数组中查找一个数，使得cur_sum减去这个数不超过k。我们使用二分查找来快速定位这个数，如果找到了满足条件的子矩阵，我们就更新结果res。最终，返回res即可。

时间复杂度: O(m^2 * n * logn)

空间复杂度: O(n)

import bisect

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        m = len(matrix)
        Row, Col = len(matrix), len(matrix[0])
        res = float('-inf')
        for ru in range(Row):
            col_sum = [0 for _ in range(Col)]
            for rd in range(ru, Row):
                for c in range(Col):
                    if matrix[rd][c] == k:
                        return k
                    col_sum[c] += matrix[rd][c]
                presum = [0]
                cur_sum = 0
                for colsum in col_sum:
                    cur_sum += colsum
                    idx = bisect.bisect_left(presum, cur_sum - k)
                    if idx < len(presum):
                        res = max(res, cur_sum - presum[idx])
                        if res == k:
                            return k
                    bisect.insort(presum, cur_sum)
        return res

Explore

前缀和加二分查找的组合用于此问题是因为此方法可以有效处理子数组/子矩阵和的问题，尤其是当需要快速获取和更新和范围内的最大值时效果显著。前缀和允许我们快速计算任意列组合的和，而二分查找则用于快速查找满足条件的最大前缀和，从而保证子矩阵的和不超过给定的k。虽然这种方法较为高效，但仍有其他方法，如动态规划或使用有序集合（如TreeSet in Java）进行优化查找，这些方法在某些情况下可能更有效。

在计算col_sum时，不论矩阵中的数值是正还是负，都直接累加到当前列的总和中。负数值自然地减少了总和，这是正确的行为，因为我们需要准确地反映每个子矩阵的实际数值和。负数的存在可能会帮助我们找到更接近k的子矩阵和，因为它们提供了减小总和的可能，从而在不超过k的前提下尽可能增大矩阵区域。

通过使用bisect_left，我们寻找的是在presum列表中第一个大于或等于`cur_sum - k`的元素。这确保了查找到的前缀和与当前的cur_sum之差是不超过k的最小可能值。这样的操作是基于presum已经排序的事实，保证了我们找到的是最接近cur_sum - k的值，从而使得子矩阵的和尽可能大但不超过k。

此检查是一个优化步骤，用于快速处理矩阵中某个元素恰好等于k的情况。这种情况不总是存在，但如果存在，那么这个元素自身就构成了和为k的最大子矩阵（因为不可能有比k还要大但不超过k的数值）。因此，这种检查虽然不是必需的，但可以在特定情况下提供性能优势，尤其是在大矩阵中，可以省去后续不必要的计算。