矩形区域不超过K的最大数值和

力扣 363. 矩形区域不超过 K 的最大数值和

题目说明

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

题目数据保证总会存在一个数值和不超过 k 的矩形区域。
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -100 <= matrix[i][j] <= 100
- -105 <= k <= 105

示例

例1

1
2
3

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

例2

1 2	输入：matrix = [[2,2,-1]], k = 3 输出：3

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，采用了动态规划加暴力的解法，动态规划是基于二维区域和检索 - 矩阵不可变的解法基础上的，让我们来看看具体如何实现的吧。

实现

class Solution {
    // 存储对应位置左上角的矩阵元素之和
    int[][] sum;

    public void NumMatrix(int[][] matrix) {
        // 矩阵的长及宽
        int row = matrix.length;
        int column = matrix[0].length;

        // 存放和的数组要比原数组多出一行一列，方便进行动态规划
        sum = new int [row + 1][column + 1];

        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= column; j++) {
                // 当前元素左上角矩阵的元素和等于上方和左方元素的和再减去重复计算的元素和再加上本格元素
                sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {

        // 返回当前r2，c2矩阵的元素和减去上方和左方元素的和再加上多减去的重复元素
        return sum[row2 + 1][col2 + 1] + sum[row1][col1] - (sum[row1][col2 + 1] + sum[row2 + 1][col1]);
    }

    // 在304. 二维区域和检索 - 矩阵不可变的基础上，直接暴力求解
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int max = -Integer.MAX_VALUE;

        NumMatrix(matrix);

        int row = matrix.length;
        int column = matrix[0].length;

        // 没有办法的暴力四层for循环
        for (int a = 0; a < row; a++) {
            for (int b = 0; b < column; b++) {
                for (int c = a; c < row; c++) {
                    for (int d = b; d < column; d++) {
                        int num = sumRegion(a, b, c, d);
                        max = num > k? max: Math.max(num, max);
                    }
                }
            }
        }

        return max;
    }
}