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)2. 解题 最好在做本题之前,先把下面链接题目读懂
链接:https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
程序员面试金典 - 面试题 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
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr() (KMP超详细讲解,sunday解法等五种方法,java实现)
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)