2021/4/22 矩形区域不超过 K 的最大数值和

题目描述

给你一个 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
-105 <= k <= 105

解题思路

本题是力扣《面试题 17.24. 最大子矩阵》的扩展题，与本题的区别是没有 k 的限制，找出数值和最大的子矩阵;
我们抛开 k 的限制，先讨论如何找到最大的子矩阵。我们可以考虑将二维数组压缩成一维数组，由上至下遍历数组，每一各自的列元素进行相加，如图

压缩完之后，一维数组求最大子序和是很简单的，我们可以使用 Kanade 算法（参照力扣题《53. 最大子序和》）轻易得到矩阵以第 1 行开头，第 n 行第？列结尾的最大子矩阵。但是有两个问题：
- 这种方式固定最后 1 行结尾，万一想要的子矩阵不包含最后一行怎么办？
- 固定了第 1 行开头，万一想要的子矩阵不包含第 1 行怎么办？

第一个问题很好解决，只需要每遍历一行时都记录一次并使用 Kanade 算法就好，如图
图片说明
第二个问题，则需要在外部多一重循环，每次循环都往下推一行，每次的起始行就不同了；
3. 讨论完无 k 值限制的最大子矩阵，我们再讨论一下加上 k 值限制的情况。这时就不能单纯使用 Kanade 算法了，因为 Kanade 算法为了得到最大值，会抛弃掉和为负数的子矩阵，但加上了最大值为 k 的限制，有些负数的子矩阵必不可少。通俗来讲，就是压缩完变成一维的数组后，Kanade 算法的起始位置其实不一定在第 1 个位置了，如上述示例 1 的图片，如果单纯求最大子矩阵，Kanade 算法就会从第 1 列开始算，结果为 4，因为抛弃了 -2。但我们应该保留 -2，那唯一的方法就只有从左往右遍历了，实际上，提示中给出矩阵最大只有 100 行 100 列，也暗示了可以使用遍历。

Java代码实现

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < rowLen; ++i) {
            int[] sum = new int[colLen];
            for (int j = i; j < rowLen; ++j) {
                for (int u = 0; u < colLen; ++u) {
                    sum[u] += matrix[j][u];
                }
                for (int u = 0; u < colLen; ++u) {
                    int cur = 0;
                    for (int v = u; v < colLen; ++v) {
                        cur += sum[v];
                        if (max < cur && cur <= k) max = cur;
                    }
                }
            }
        }
        return max == Integer.MIN_VALUE ? -1 : max;
    }
}