【数据结构-二位前缀和】【二分查找】【罗列优化】力扣1292. 元素和小于等 ...

给你一个大小为 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
二分查找+前缀和

1. class Solution {
2. public:
3.     int getIt(const vector<vector<int>>&sum, int x1, int y1, int x2, int y2){
4.             return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
5.         }
7.     int maxSideLength(vector<vector<int>>& mat, int threshold) {
8.         
9.         int m = mat.size(), n = mat[0].size();
10.         vector<vector<int>> sum(m+1, vector<int>(n+1));
11.         for(int i = 0; i < m; i++){
12.             for(int j = 0; j < n; j++){
13.                 sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + mat[i][j];
14.             }
15.         }
17.         int l = 1, r = min(m, n);
18.         int ans = 0;
19.         while(l <= r){
20.             int mid = (l+r)/2;
21.             bool find = false;
22.             for(int i = 1; i <= m - mid + 1; i++){
23.                 for(int j = 1; j <= n - mid + 1; j++){
24.                     if(getIt(sum, i, j, i+mid-1, j+mid-1)<=threshold){
25.                         find = true;
26.                     }
27.                 }
28.             }
29.             if(find){   //如果能够找到符合条件的该边长正方形，那么移动l到mid右边，去查找更大边长正方形
30.                 ans = mid;
31.                 l = mid+1;
32.             }else{
33.                 r = mid-1;
34.             }
35.         }
36.         return ans;
37.     }
38. };

复制代码

时间复杂度：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开始，要注意的是这时候正方形左上角并不是[1,1]，而是[0,0]，由于i和j的范围是从1到n - mid + 1（包含），也就是i和j是前缀和相关。如果找到了如许一个正方形，阐明这边长是目前可实现的最大的，那么计入输出结果ans中，然后去探求更大边长正方形是否可行，如果这个边长的正方形没有找到一个符合条件小于threshold，那么r就要酿成mid-1，在接下来mid又是l和r的中点，然后去看mid可行不可行，直到l>r，然后才结束。
如果连边长为1正方形都没有找到符合的，那么返回ans的原始值0。
优化：罗列

1. class Solution {
2. public:
3.     int getIt(const vector<vector<int>>&sum, int x1, int y1, int x2, int y2){
4.             return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
5.         }
7.     int maxSideLength(vector<vector<int>>& mat, int threshold) {
8.         
9.         int m = mat.size(), n = mat[0].size();
10.         vector<vector<int>> sum(m+1, vector<int>(n+1));
11.         for(int i = 0; i < m; i++){
12.             for(int j = 0; j < n; j++){
13.                 sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + mat[i][j];
14.             }
15.         }
17.         int r = min(m, n),ans = 0;
18.         for(int i = 1; i <= m; i++){
19.             for(int j = 1; j <= n; j++){
20.                 for(int c = ans + 1;c <= r; c++){
21.                     if(i+c-1<=m && j+c-1<=n && getIt(sum, i, j, i+c-1, j+c-1)<= threshold){
22.                         ans++;
23.                     }else{
24.                         break;
25.                     }
26.                 }
27.             }
28.         }
29.         return ans;
31.     }
32. };

复制代码

时间复杂度：O(MN)。这看上去很不可思议，但它确实比方法一中二分查找的时间复杂度更低。
空间复杂度：O(MN)。
在这个优化中，我们直接罗列1开始的边长，当存在这个正方形的时候，就不用遍历接下来这个边长的正方形了，让边长+1，继承查找有没有符合这个边长的长方形，一旦遍历完所有正方形的左上角位置都没有找到，那么就不用接下来的循环，ans这时候就是最大的符合条件的正方形边长。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。