1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k/description/

2.解题方法

2.1.解题思路

枚举+前缀和+有序集合+二分查找

2.2.解题步骤

第一步，枚举行的两两组合，记两行分别为r1和r2（保证r1<=r2）

第二步，对于每个行组合。使用数组arr维护两行之间所有列的元素和；并使用preSum维护当前的前缀和；sl维护已经遍历的区域的前缀和的有序集合

• 2.1.更新两行之间所有列的元素和数组arr

• 2.2.遍历所有的列，更新维护变量

  • 2.2.1.更新当前的前缀和preSum

  • 2.2.2.从有序集合sl中使用二分查找找到第一个满足大于或等于preSum-k的元素，记为sum1

  • 2.2.3.如果sum1存在，则根据preSum-sum1更新result

  • 2.2.4.更新有序集合sl

第三步，返回result

3.解题代码

python代码

from sortedcontainers import SortedList

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        # 思路：枚举+前缀和+有序集合+二分查找
        m, n = len(matrix), len(matrix[0])
        # 第一步，枚举行的两两组合，记两行分别为r1和r2（保证r1<=r2）
        result = -inf
        for r1 in range(m):
            arr = [0] * n
            for r2 in range(r1, m):
                # 第二步，对于每个行组合。使用数组arr维护两行之间所有列的元素和；并使用preSum维护当前的前缀和；sl维护已经遍历的区域的前缀和的有序集合
                sl = SortedList([0])
                # 2.1.更新两行之间所有列的元素和数组arr
                for c in range(n):
                    arr[c] += matrix[r2][c]
                # 2.2.遍历所有的列，更新维护变量
                preSum = 0
                for c in range(n):
                    # 2.2.1.更新当前的前缀和preSum
                    preSum += arr[c]
                    # 2.2.2.从有序集合sl中使用二分查找找到第一个满足大于或等于preSum-k的元素，记为sum1
                    index = sl.bisect_left(preSum - k)
                    # 2.2.3.如果sum1存在，则根据preSum-sum1更新result
                    if index < c + 1:
                        sum1 = sl[index]
                        result = max(result, preSum - sum1)
                    # 2.2.4.更新有序集合sl
                    sl.add(preSum)
        # 第三步，返回result
        return result

4.执行结果