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

题目

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

时间复杂度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);
 }

扩展阅读

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17