C++前缀和算法应用：矩形区域不超过 K 的最大数值和

基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例

题目

给你一个 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

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-105 <= k <= 105

分析

二维前缀和

vPreSum[r][c] 记录以(0,0)开始，宽高为c r的矩形和。vPreSum[r][c] = vPreSum[r - 1][c] + vPreSum[r][c - 1] + matrix[r - 1][c - 1] - vPreSum[r - 1][c - 1];
在这里插入图片描述


vPreSum[r - 1][c]	绿色实心矩形的和
vPreSum[r][c - 1]	蓝色空心矩形
matrix[r - 1][c - 1]	黄色矩形
vPreSum[r - 1][c - 1]	蓝绿重叠部分

时间复杂度O(nnn*logn)

枚举所有矩形，时间复杂度是O(n^4)，超时。三层循环，第一层和第二层循环，枚举左右。第三层循环枚举下，setSum记录了所有合法的t的构成的矩形(left,0,right,t-1)的和。显然iLeftRight - setSum任意元素的值，就是(left,t,right,row)矩形的和。iLeftRight 是矩形(left,0,right,row)的和。对setSum 进行二分。

源码

class Solution {
public:
int maxSumSubmatrix(vector<vector>& matrix, int k) {
m_r = matrix.size();
m_c = matrix.front().size();
vector<vector> vPreSum(m_r+1,vector(m_c+1,0)); //vPreSum[r][c] 以(0,0)开始，宽高为c r的矩形
for (int r = 1; r <= m_r; r++)
{
for (int c = 1; c <= m_c; c++)
{
//令r=1,c=1 vPreSum[1][1] = 0 +0 + matrix[0][0] -0
//令r=2,c=2 vPreSum[2][2] = vPreSum[1][2] +vPreSum[2][1] + matrix[1][1] + vPreSum[1][1]
vPreSum[r][c] = vPreSum[r - 1][c] + vPreSum[r][c - 1] + matrix[r - 1][c - 1] - vPreSum[r - 1][c - 1];
}
}
int iMin = INT_MIN;
//vector<vector> vDebug(m_r, vector(m_c,INT_MIN));
for (int left = 0; left < m_c ; left++ )
{
for (int right = left ; right < m_c; right++ )
{
//row和right 是右下角的坐标
set setSum = { 0 };
for (int row = 0; row < m_r; row++)
{
const int iLeftRight = vPreSum[row + 1][right + 1]

vPreSum[row + 1][left];
//iLeftRight - x <=k ==> -x <= k - iLeftRight ==> x >= iLeftRight-k
auto it = setSum.lower_bound(iLeftRight - k);
if (setSum.end() != it)
{
iMin = max(iMin, iLeftRight - *it);
//vDebug[row][right] = iLeftRight - *it;
}
setSum.emplace(iLeftRight);
}
}
}
return iMin;
}
int m_r, m_c;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector<vector> matrix = { {1, 2, 3}, { 4,5,6 } };
int k = 2;
auto res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 2);
matrix = { {1, 0, 1}, { 0,-2,3 } };
k = 2;
res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 2);
matrix = { {2,2,-1} };
k = 3;
res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 3);
CConsole::Out(res);
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛