题目描述

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

(二维前缀和 + 暴力枚举) $\mathcal O(n^2m^2)$

• 枚举上下左右边界，从而枚举出每个矩形，利用预处理的二维前缀和来求矩阵的和来更新答案

Java 代码

class Solution {
    public int maxSumSubmatrix(int[][] a, int k) {
        int n = a.length, m = a[0].length;
        int[][] s = new int[n+1][m+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i-1][j-1];
            }
        }
        int res = Integer.MIN_VALUE;
        // 左上角(i, v), 右下角(j, w)
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= n; j++){
                for(int v = 1; v <= m; v++){
                    for(int w = v; w <= m; w++){
                        int sum = s[j][w] - s[i-1][w] - s[j][v-1] + s[i-1][v-1];
                        if(sum <= k){
                            res = Math.max(res, sum);
                        }
                    }
                }
            }
        }
        return res;
    }
}

算法2

(一维前缀和 + 平衡树/二分查找) $\mathcal O(n^2m\log m)$

• 枚举上下边界，按列求前缀和，即可把问题转化为在数组a中寻找一个最大区间和使得这个和不超过k，即Sr - Sl <= k，转化为Sl >= Sr - k，要使得Sr - Sl最大，必须找到使得Sl >= Sr - k成立的最小Sl
• 遍历前缀和数组，用平衡树维护每个值，并且找到使得Sl >= Sr - k成立的最小Sl，并且把Sr插入平衡树中，为避免第一个数需要特判，往平衡树中插入0作为哨兵统一处理

Java代码

class Solution {
    public int maxSumSubmatrix(int[][] a, int k) {
        int n = a.length, m = a[0].length;
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            int[] s = new int[m];
            for(int j = i; j < n; j++){
                for(int u = 0; u < m; u++){
                    s[u] += a[j][u];
                }
                // Sr - Sl <= k -> Sl >= Sr - k
                // 找到大于等于Sr-k的最小Sl，使得Sr-Sl最大
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                int sum = 0;
                for(int x: s){
                    sum += x;
                    Integer sl = set.ceiling(sum - k);
                    if(sl != null){
                        res = Math.max(res, sum - sl);
                    }
                    set.add(sum);
                }
            }
        }
        return res;
    }
}