LeetCode 363. 矩形区域不超过 K 的最大数值和(DP+set二分查找)

1. 题目 【LeetCode 363. 矩形区域不超过 K 的最大数值和(DP+set二分查找)】给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不大于 k 的最大矩形和。

示例: 输入: matrix = [[1,0,1],[0,-2,3]], k = 2 输出: 2 解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2, 且 2 是不超过 k 的最大数字(k = 2)。说明: 矩阵内的矩形区域面积必须大于 0。 如果行数远大于列数,你将如何解答呢?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题 最好在做本题之前,先把下面链接题目读懂
程序员面试金典 - 面试题 17.24. 最大子矩阵(转成一维最大子序和 DP)
  • 本题说行比较多,那么按列来压扁,两重循环,遍历所有的列组合
  • 对每种列组合,压扁后的 m (行数)个和,先求最大子序和(按照上题方法)
  • 如果最大连续子序和 == k,返回 k,< k 进行下一个组合
  • 如果子序和 > k ,那还需要找是否有 <= k 的呢?将前缀和 prefix 插入set(初始有0,防止prefix 一开始就是 k 的情况)
  • 二分查找 prefix-k 的下限 lb,如果存在,则lb >= prefix-k, 两个前缀和做差就是连续子序列的和 SUM = prefix - lb <= k,更新最大值
class Solution { public: int maxSumSubmatrix(vector>& mat, int k) { if(mat.empty() || mat[0].empty()) return 0; int m = mat.size(), n = mat[0].size(), i, j1, j2; int sum, tempmax, maxsum = INT_MIN, prefix; vector sumCols(m); for(j1 = 0; j1 < n; ++j1) { sumCols.clear(); sumCols.resize(m); for(j2 = j1; j2 < n; ++j2) { //列的左右边界组合 for(i = 0; i < m; ++i) sumCols[i] += mat[i][j2]; //行向求和 sum = tempmax = INT_MIN; for(i = 0; i < m; ++i) { //对上面的和,求最大连续子序列和,DP if(sum > 0) sum += sumCols[i]; else sum = sumCols[i]; tempmax = max(sum, tempmax); //临时的最大子序列和 if(sum <= k)//更新答案 maxsum = max(maxsum, sum); } if(tempmax == k || maxsum==k) return k; //找到上限直接返回 if(tempmax < k)//最大连续子序列和小于 k,进行下一轮 continue; //最大连续子序列和 大于 k,还要继续查找 有可能 <= k 的 set s; s.insert(0); //第一个就是k的时候,可以找到 prefix = 0; //利用前缀和,在set中二分查找 for(i = 0; i < m; ++i) { prefix += sumCols[i]; auto it = s.lower_bound(prefix-k); s.insert(prefix); if(it != s.end()) { int SUM = prefix-(*it); if(SUM > maxsum) maxsum = SUM; } if(maxsum == k) return k; } } } return maxsum; } };

60 ms 9.3 MB

    推荐阅读