363、矩形区域不超过K的最大数值和
给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。
示例:
输入: matrix = [[1,0,1],[0,-2,3]], k = 2
输出: 2
解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
说明：
- 矩阵内的矩形区域面积必须大于 0。
- 如果行数远大于列数，你将如何解答呢？
题解
1、最大前缀和的二维形式
求每一行的前缀和
穷举所有矩形，求其和
- 更新最大值
- 若求的的值等于k, 直接返回
代码
// c++
class Solution {
public:
// n行数，m列数
// O(m^2 * nlog(n)) 对所有可能的左右边界，在前缀和的基础上求小于k的最大连续子数组和
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), m = matrix[0].size();
// 预处理前缀和，求每一行的前缀和
vector<vector<int>> v(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
v[i][j] = v[i][j - 1] + matrix[i - 1][j - 1];
}
}
// 两个for遍历所有可能的左右边界
int res = INT_MIN;
// 对于每一列
for (int l = 1; l <= m; l++) {
// 从第l列开始，遍历剩余的列
for (int r = l; r <= m; r++) {
// 存set，set查询lower_bound O(log(n))
set<int> st;
st.insert(0);
int cur = 0;
// 对于每一行，求可能的矩阵
for (int i = 1; i <= n; i++) {
// 第i-1行中l-r直接的数之和
int now = v[i][r] - v[i][l - 1];
cur += now;
// 对于当前的前缀和，找数中大于等于cur-k的最小元素
// 设找到的数为p，则p大于等于cur-k，必有 cur - p <= k
// 所有最小的p，使得cur-p的值最大，且该值小于等于k
// lower_bound()返回值是一个迭代器,返回指向大于等于key的第一个值的位置
auto it = st.lower_bound(cur - k);
// 更新最大值
if (it != st.end()) res = max(res, cur - *it);
st.insert(cur);
// 找到最大值，提前结束
if (res == k) return res;
}
}
}
return res;
}
};
// 作者：zhenying
// 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/cpp-86-qian-zhui-he-chu-li-by-zhenying/
- 16ms
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
if (n == 0) return 0;
int m = matrix[0].size();
if (m == 0) return 0;
int res = INT_MIN;
// 对于所有的列
for (int s = 0; s < m; ++s) {
// 申请一个大小等于行数的数组
vector<int> rowSum(n, 0);
// 从第s列开始的所有列
for (int e = s; e < m; ++e) {
// 记录矩阵和
int maxSum = 0;
// 对于行求和
for (int i = 0, acc = 0; i < n; ++i) {
rowSum[i] += matrix[i][e];
acc += rowSum[i];// 累加
// 这个表达式有点意思
acc <= k && res < acc ? res = acc : 0;
acc < 0 ? acc = 0 : maxSum = max(maxSum, acc);
}
// 找到最大解，提前结束
if (res == k) return k;
// 否则继续循环，继续叠加
if (maxSum < k) continue;
// 集合
set<int> hash{0};
for (int i = 0, acc = 0; i < n; ++i) {
acc += rowSum[i];// 累加
// 求hash中第一个大于等于acc-k的下标
auto iter = hash.lower_bound(acc - k);
iter != hash.end() && res < acc - *iter ? res = acc - *iter : 0;
hash.insert(acc);
}
// 提前结束
if (res == k) return k;
}
}
return res;
}
};
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
