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

题目描述

描述转载自力扣《363. 矩形区域不超过 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

解题思路

1. 本题是力扣《面试题 17.24. 最大子矩阵》 的扩展题，与本题的区别是没有 k 的限制，找出数值和最大的子矩阵;
2. 我们抛开 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;
    }
}