目录

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

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

Difficulty: 困难

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

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

示例 1:

https://i.loli.net/2021/04/30/Id4qFm7B1ongP8T.png

输入: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 = \text{matrix.length}$
  • $n = \text{matrix[i].length}$
  • $1 \leq m, n \leq 100$
  • $-100 \leq \text{matrix[i][j]} \leq 100$
  • $-10^5 \leq k \leq 10^5$

进阶:如果行数远大于列数,该如何设计解决方案?

解法一

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

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

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

https://static.imlgw.top/blog/20210505/7nujFBoFs95s.png

我们要求的矩形面积是 $s[r]-s[l]$ ,结合这题的要求就是 $s[r]-s[l] \leq k$ ,所以我们要求的就是 $r$ 前面满足 $s[l] \geq s[r]-k$ 的最小 $s[l]$ ,显然只要我们将前面的所有元素 $s[i]$ 有序的存储下来,就可以使用二分来查找,这里我们就不必再造轮子了,直接借助TreeSet,底层结构是红黑树,查询复杂度 $O(\log{n})$ ,整体复杂度 $O(m^2n\log{n})$ 。进阶的做法多判断一下就行了,对复杂度没有本质的影响,不多写了。

代码实现如下:

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;
    }
}