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

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

Difficulty: 困难

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

提示：

进阶：如果行数远大于列数，该如何设计解决方案？

解法一

这个题给了我很大的启发，对枚举方法又多了点认识，这题常规暴力的做法是直接枚举所有的矩形，然后判断，结合二维前缀和，时间复杂度，已经在 T 的边缘了，所以我们要优化一下算法。

这里其实就涉及到一个优化枚举的一般思路，前面做过的 最大子序和 就可以用类似的枚举优化的思路（这题有更简单的 dp 做法），常规的暴力枚举可以借助前缀和枚举所有的子区间的和，求一个最大值，但是这样时间复杂度将会是，那么我们就可以考虑优化枚举方法，我们最终的目标是求最大的，所以我们可以考虑将固定，然后借助一些数据结构，比如小根堆，搜索树（其实一个变量就行了。..）直接求出固定时，前面最小的，如此只需要遍历一遍就能得到最大的子序和。

回到这个题，上面最大子序和是一维的，这里是二维的，我们可以将其抽象为一维的，我们枚举所有矩形其实就是在枚举矩形的四条边，但是时间复杂度过高，那么我们可以采用前面的优化思路，将三条边固定

我们要求的矩形面积是，结合这题的要求就是，所以我们要求的就是前面满足的最小，显然只要我们将前面的所有元素有序的存储下来，就可以使用二分来查找，这里我们就不必再造轮子了，直接借助TreeSet，底层结构是红黑树，查询复杂度，整体复杂度。进阶的做法多判断一下就行了，对复杂度没有本质的影响，不多写了。

代码实现如下：

import java.util.*;

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int[][] s = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                s[i][j] = matrix[i-1][j-1] + s[i-1][j] + s[i][j-1] -s[i-1][j-1];
            }
        }
        TreeSet<Integer> set = new TreeSet<>();
        int res = -0x3f3f3f3f;
        for (int u = 1; u <= m; u++) {
            for (int d = u; d <= m; d++) {
                set.clear();
                set.add(0);
                //0 lv rv, rv-lv <= k  lv >= rv-k
                for (int r = 1; r <= n; r++) {
                    int rv = s[d][r] - s[u-1][r];
                    Integer lv = set.ceiling(rv-k);
                    set.add(rv);
                    if (lv == null) continue;
                    res = Math.max(res, rv-lv);
                }
            }
        }
        return res;
    }
}