LeetCode363:寻找不超过K的最大子矩阵和【固定边界+逐步求和+有序列表查询】

在LeetCode 363题目中，我们需要在一个非空整数矩阵中找到一个子矩阵，其所有元素之和不超过给定值K，同时这个和尽可能大。

直接使用O(m^2n^2)的时间复杂度来枚举所有可能的子矩阵会因为效率过低而超时。因此，我们采用了一种更高效的策略：

• 首先，固定矩阵的上下边界，这样可以将问题简化为在一维数组中寻找符合条件的子数组。
• 接着，从左向右遍历每列，计算当前固定边界的累积和。
• 使用SortedList（来自sortedcontainers库）来存储这些累积和，以便能够高效地查询。
• 对于每个新的累积和，通过二分查找技术，在SortedList中寻找第一个大于等于当前累积和减去K的值，以此来更新最大子矩阵和。

这种方法的时间复杂度为O(m^2n log n)，大大提高了处理大规模数据的能力。

from sortedcontainers import SortedList
class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        from math import inf
        ans = -inf
        m, n = len(matrix), len(matrix[0])
        # 枚举上下边界
        for up in range(m):
            col_sum = [0] * n
            for down in range(up, m):
                # 计算固定上下边界后的每列和
                for c in range(n):
                    col_sum[c] += matrix[down][c]
                # 使用SortedList记录每一步的累积和
                stl = SortedList([0])  # 初始化时包含0
                tmp = 0
                for v in col_sum:
                    tmp += v
                    # 查找大于等于tmp-k的第一个位置
                    idx = stl.bisect_left(tmp - k)
                    if idx                         ans = max(ans, tmp - stl[idx])
                    stl.add(tmp)
        return ans

通过固定上下边界的方法，我们将原本四重循环的问题转换成了一个更易处理的形式。利用SortedList进行高效查询，不仅保证了算法的正确性，也显著提升了执行效率。此方法适用于处理较大规模的数据集，但在实际应用中仍需注意内存消耗的问题。