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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 思路

// 枚举所有 的小矩形

# 解法


class Solution {
    // 枚举所有 的小矩形


    public int maxSumSubmatrix(int[][] matrix, int k) {

        int xlen = matrix.length;
        if(xlen == 0){
            return 0;
        }
        int ylen = matrix[0].length;
        int[][] sum = new int[xlen + 1][ylen + 1];
        for(int i = 0; i < xlen; i++) {
            for (int j = 0; j < ylen; j++){
                sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] + matrix[i][j] - sum[i][j];
                System.out.println(sum[i+1][j+1]);
            }
        }
         int ans = Integer.MIN_VALUE;
        for (int i = 0; i <= xlen; i++) {
            for (int j = 0; j <= ylen; j++) {
                for (int p = i; p < xlen; p++) {
                    for (int q = j; q < ylen; q++) {
                        int cur = sum[p+1][q+1] - sum[i][q+1] - sum[p+1][j] + sum[i][j];
                        if (cur <= k) {
                            ans = Math.max(ans, cur);
                        } 
                    }
                }
            }
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 总结

分析出几种情况，然后分别对各个情况实现

← 设计推特水壶问题→