本文涉及的基础知识点

C++二分查找

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode1292. 元素和小于等于阈值的正方形的最大边长

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4

输出：2

解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。

示例 2：

输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1

输出：0

提示：

m == mat.length

n == mat[i].length

1 <= m, n <= 300

0 <= mat[i][j] <= 10⁴

0 <= threshold <= 10⁵

二分查找、前缀和

预处理好前缀和后，可以在O(1)的时间内，计算矩形之和。

二分查找类型：寻找末端

Check函数的参数返回：[1,min(n,m)]

异常处理：如果Check(ret)不成立，则返回0。

Check函数：枚举各矩形的左上角，如果和小于等于阈值，返回true。否则返回false。Check函数的时间复杂度：O(nm)

总时间复杂度：O(log(min(n,m))nm)

代码

核心代码

<code>template<class T = int>

class CPreSum2 { -- -->

public:

template<class _Pr>

CPreSum2(int rowCnt, int colCount, _Pr pr) :m_iRowCnt(rowCnt), m_iColCnt(colCount) {

m_vSum.assign(rowCnt + 1, vector<int>(colCount + 1));

for (int r = 0; r < rowCnt; r++) {

for (int c = 0; c < colCount; c++) {

m_vSum[r + 1][c + 1] = m_vSum[r][c + 1] + m_vSum[r + 1][c] - m_vSum[r][c] + pr(r, c);

}

}

}

T Get(int left, int top, int right, int bottom)const {

return m_vSum[bottom + 1][right + 1] - m_vSum[top][right + 1] - m_vSum[bottom + 1][left] + m_vSum[top][left];

}

T GetTopLeft(int left, int top) { return Get(left, top, m_iColCnt - 1, m_iRowCnt - 1); }

vector<vector<T>> m_vSum;

const int m_iRowCnt, m_iColCnt;

};

template<class INDEX_TYPE>

class CBinarySearch

{

public:

CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) { }

template<class _Pr>

INDEX_TYPE FindFrist( _Pr pr)

{

auto left = m_iMin - 1;

auto rightInclue = m_iMax;

while (rightInclue - left > 1)

{

const auto mid = left + (rightInclue - left) / 2;

if (pr(mid))

{

rightInclue = mid;

}

else

{

left = mid;

}

}

return rightInclue;

}

template<class _Pr>

INDEX_TYPE FindEnd( _Pr pr)

{

int leftInclude = m_iMin;

int right = m_iMax + 1;

while (right - leftInclude > 1)

{

const auto mid = leftInclude + (right - leftInclude) / 2;

if (pr(mid))

{

leftInclude = mid;

}

else

{

right = mid;

}

}

return leftInclude;

}

protected:

const INDEX_TYPE m_iMin, m_iMax;

};

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

m_r = mat.size();

m_c = mat.front().size();

CPreSum2<int> preSum(m_r, m_c, [&](const int& r, const int& c) { return mat[r][c]; });

auto Check = [&](int mid) {

for (int r = 0; r+mid <= m_r; r++) {

for (int c = 0; c+mid <= m_c; c++) {

const int sum = preSum.Get(c, r, c + mid - 1, r + mid - 1);

if (sum <= threshold) { return true; }

}

}

return false;

};

return CBinarySearch<int>(0, min(m_r, m_c)).FindEnd(Check);

}

int m_r, m_c;

};

单元测试

vector<vector<int>> mat;

int threshold;

TEST_METHOD(TestMethod13)

{

mat = { { 1,1,3,2,4,3,2},{ 1,1,3,2,4,3,2},{ 1,1,3,2,4,3,2} }, threshold = 4;

auto res = Solution().maxSideLength(mat, threshold);

AssertEx(2, res);

}

TEST_METHOD(TestMethod14)

{

mat = { { 2,2,2,2,2},{ 2,2,2,2,2},{ 2,2,2,2,2},{ 2,2,2,2,2},{ 2,2,2,2,2} }, threshold = 1;

auto res = Solution().maxSideLength(mat, threshold);

AssertEx(0, res);

}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

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

如无特殊说明，本算法用**C++**实现。