leetcode 363.矩形区域不超过K的最大数值和，通过此题好好了解前缀和的各种应用和变化

题目描述

给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。

示例:

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

矩阵内的矩形区域面积必须大于 0。 如果行数远大于列数，你将如何解答呢？

思路

这道题目的思路是固定左右边界，对行进行前缀和和二分查找。

我们知道，前缀和可以让我们O(1)的时间复杂度知道任何区间和。

前缀和的典型构建方法：

pre = [0]
p = 0
for n in nums:
    p += n
    pre.append(p)

比如我们想知道i,j之间的区间和，包括i，j索引的话，我们的方法是pre[j+1] - pre[i]。

通过前缀和的变种，我们可以解决一些新的问题。

我们将前缀和变成hash set，就可以快速判断是否有一个区间和等于target。

我们可以插入排序的方法替换掉单纯的append，使前缀和有序，这样就可以用二分查找找到最接近某个target的区间和。

这道题目就利用了第二种想法。

我们固定左右边界，left和right，先将left到right之间的每一行的所有数值累加。这样我们就有了一列数。通过固定所有这样的left和right我们也就枚举了矩形所有的左边界和右边界。接着我们用第二种方法，边构建前缀和，编计算最接近target的矩形面积。

其大致代码如下：

pre = [0]
p = 0
for r in total:
    p += r
    loc = bisect.bisect_left(pre, p - k)
    if loc != len(pre):
        res = max(res, p - pre[loc])
    bisect.insort(pre, p)

有了这段代码，再加上我们固定左右边界的代码，我们就可以解决这个问题。计算一下复杂度。

固定左右边界需要O(n^2)的时间复杂度，n为矩形的列数。生成前缀和遍历需要O(m)，m为矩阵的行数，搜索是O(logm)的，但是插入是O(m)的。所以总体上还是O(n^2m^2)的。但是常数项比较低。

总体代码如下

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        total = [0] * m
        res = float('-inf')
        for left in range(n):
            total[:] = [0] * m
            for right in range(left, n):
                for i in range(m):
                    total[i] += matrix[i][right]
                pre = [0]
                p = 0
                for r in total:
                    p += r
                    loc = bisect.bisect_left(pre, p - k)
                    if loc != len(pre):
                        res = max(res, p - pre[loc])
                    bisect.insort(pre, p)
        return res

另一道相似题目

1546. 和为目标值的最大数目不重叠非空子数组数目

给你一个数组 nums 和一个整数 target 。

请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。

示例 1：

输入：nums = [1,1,1,1,1], target = 2 输出：2 解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。 示例 2：

输入：nums = [-1,3,5,1,4,2,-9], target = 6 输出：2 解释：总共有 3 个子数组和为 6 。 ([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。 示例 3：

输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10 输出：3 示例 4：

输入：nums = [0,0,0], target = 0 输出：3

提示：

1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 0 <= target <= 10^6

这道题目就是使用了第一种前缀和的变化，并应用了贪心的思想。

一旦发现target在区间和中，我们就重新统计前缀和。示例代码如下：

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        pre = {0}
        p = 0
        res = 0
        for n in nums:
            p += n
            if p - target in pre:
                res += 1
                pre = {0}
                p = 0
            else:
                pre.add(p)
        return res