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

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 做法),常规的暴力枚举可以借助前缀和枚举所有的子区间的和,求一个最大值,但是这样时间复杂度将会是,那么我们就可以考虑优化枚举方法,我们最终的目标是求最大的,所以我们可以考虑将固定,然后借助一些数据结构,比如小根堆,搜索树(其实一个变量就行了。..)直接求出固定时,前面最小的,如此只需要遍历一遍就能得到最大的子序和。

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

mark

我们要求的矩形面积是,结合这题的要求就是,所以我们要求的就是前面满足的最小,显然只要我们将前面的所有元素有序的存储下来,就可以使用二分来查找,这里我们就不必再造轮子了,直接借助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;
}
}
  • 本文标题:LeetCode363. 矩形区域不超过 K 的最大数值和
  • 本文作者:Resolmi
  • 创建时间:2021-04-30 00:00:00
  • 本文链接:https://imlgw.top/2021/04/30/a7703ba4/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论