【数据结构-二位前缀和】【二分查找】【罗列优化】力扣1292. 元素和小于等于阈值的正方形的最大边长
给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有如许的正方形区域，则返回 0 。
示例 1：
https://i-blog.csdnimg.cn/direct/b980b54aa9924726990ec1dd9063e8c9.png
输入：mat = [,,], threshold = 4
输出：2
解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。
示例 2：
输入：mat = [,,,,], threshold = 1
输出：0
二分查找+前缀和
class Solution {
public:
int getIt(const vector<vector<int>>&sum, int x1, int y1, int x2, int y2){
return sum - sum - sum + sum;
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat.size();
vector<vector<int>> sum(m+1, vector<int>(n+1));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
sum = sum + sum - sum + mat;
}
}
int l = 1, r = min(m, n);
int ans = 0;
while(l <= r){
int mid = (l+r)/2;
bool find = false;
for(int i = 1; i <= m - mid + 1; i++){
for(int j = 1; j <= n - mid + 1; j++){
if(getIt(sum, i, j, i+mid-1, j+mid-1)<=threshold){
find = true;
}
}
}
if(find){ //如果能够找到符合条件的该边长正方形，那么移动l到mid右边，去查找更大边长正方形
ans = mid;
l = mid+1;
}else{
r = mid-1;
}
}
return ans;
}
};
时间复杂度：O(MN∗logmin(M,N))。二分查找的次数为 O(logmin(M,N))，在每次二分查找中，需要罗列所有边长为 c’ 的矩形，数量为 O(MN)，因此总时间复杂度为 O(MN∗logmin(M,N))。
空间复杂度：O(MN)。
这道标题运用了两个知识点，一个是前缀和在二维中的运用，第二个是二分查找来探求最大边长。
首先maxSideLength函数中先计算前缀和，然后再看getIt函数中，是用于接下来通过前缀和来计算正方形内的元素和。
这道题的精髓在于二分查找的利用，由于我们要找到最大的边长，那么我们是不是通常来想，需要遍历从1到矩阵较短边长度的正方形边长，然后把边长一个个去矩阵中探求是否有符合的正方形。这时候我们通过二分查找，l指向1，r指向矩阵较短的边的长度，然后mid就是他们的中点(l+r)/2。然后我们这时候就要去找是否有符合的正方形，从i=1和j=1开始，要注意的是这时候正方形左上角并不是，而是，由于i和j的范围是从1到n - mid + 1（包含），也就是i和j是前缀和相关。如果找到了如许一个正方形，阐明这边长是目前可实现的最大的，那么计入输出结果ans中，然后去探求更大边长正方形是否可行，如果这个边长的正方形没有找到一个符合条件小于threshold，那么r就要酿成mid-1，在接下来mid又是l和r的中点，然后去看mid可行不可行，直到l>r，然后才结束。
如果连边长为1正方形都没有找到符合的，那么返回ans的原始值0。
优化：罗列
class Solution {
public:
int getIt(const vector<vector<int>>&sum, int x1, int y1, int x2, int y2){
return sum - sum - sum + sum;
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat.size();
vector<vector<int>> sum(m+1, vector<int>(n+1));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
sum = sum + sum - sum + mat;
}
}
int r = min(m, n),ans = 0;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
for(int c = ans + 1;c <= r; c++){
if(i+c-1<=m && j+c-1<=n && getIt(sum, i, j, i+c-1, j+c-1)<= threshold){
ans++;
}else{
break;
}
}
}
}
return ans;
}
};
时间复杂度：O(MN)。这看上去很不可思议，但它确实比方法一中二分查找的时间复杂度更低。
空间复杂度：O(MN)。
在这个优化中，我们直接罗列1开始的边长，当存在这个正方形的时候，就不用遍历接下来这个边长的正方形了，让边长+1，继承查找有没有符合这个边长的长方形，一旦遍历完所有正方形的左上角位置都没有找到，那么就不用接下来的循环，ans这时候就是最大的符合条件的正方形边长。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]