C++中求和小于等于阈值的正方形最大边长

假设我们有一个 m x n 的矩阵 mat 和一个整数阈值。我们需要找到一个和小于等于给定阈值的正方形的最大边长，如果不存在这样的正方形，则返回 0。例如，如果输入如下：

并且阈值为 4，则输出为 2，因为存在两个边长为 2 的正方形，因此最大值为 2。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个名为 ok 的方法，它将接收 x、矩阵 m 和阈值 th 作为参数。
• 设置 curr := 0
• 对于 i 从 x – 1 到 mat 的行数 – 1
  • 对于 c 从 x – 1 到 mat 的列数 – 1
    • curr := mat[r, c]
    • 如果 c – x >= 0，则将 curr 减去 mat[r, c – x]
    • 如果 r – x >= 0，则将 curr 减去 mat[r - x, c]
    • 如果 c – x >= 0 且 r – x >= 0，则将 curr 加上 mat[r – x, c - x]
    • 如果 curr <= th，则返回 true
• 返回 false
• 在主方法中，它将接收矩阵和阈值作为参数。
• r := 行数，c := 列数，low := 1，high := r 和 c 的最小值，ans := 0
• 对于 i 从 1 到 c – 1
  • 对于 j 从 0 到 c – 1
    • 将 mat[j, i] 加上 mat[j, i - 1]
• 对于 i 从 1 到 r – 1
  • 对于 j 从 0 到 c – 1
    • 将 mat[j, i] 加上 mat[ i - 1,j]
• 当 low <= high 时
  • mid := low + (high - low) / 2
  • 如果 ok(mid, mat, th) 为真，则 ans := mid 且 low := mid + 1，否则 high := mid – 1
• 返回 ans

示例（C++）

让我们看一下下面的实现，以便更好地理解：

 在线演示

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   bool ok(int x, vector < vector<int> >& mat, int th){
      lli current = 0;
      for(int r = x - 1; r < mat.size(); r++){
         for(int c = x - 1; c < mat[0].size(); c++){
            current = mat[r][c];
            if(c - x >= 0)current -= mat[r][c-x];
            if(r -x >= 0)current -= mat[r - x][c];
            if(c - x >= 0 && r - x >= 0)current += mat[r-x][c-x];
            if(current <= th)return true;
         }
      }
      return false;
   }
   int maxSideLength(vector<vector<int>>& mat, int th) {
      int r = mat.size();
      int c = mat[0].size();
      int low = 1;
      int high = min(r, c);
      int ans = 0;
      for(int i = 1; i < c; i++){
         for(int j = 0; j < r; j++){
            mat[j][i] += mat[j][i - 1];
         }
      }
      for(int i = 1; i < r; i++){
         for(int j = 0; j < c; j++){
            mat[i][j] += mat[i - 1][j];
         }
      }
      while(low <= high){
         int mid = low + ( high - low ) / 2;
         if(ok(mid, mat, th)){
            ans = mid;
            low = mid + 1;
         }
         else{
            high = mid - 1;
         }
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{1,1,3,2,4,3,2},{1,1,3,2,4,3,2},{1,1,3,2,4,3,2}};
   Solution ob;
   cout << (ob.maxSideLength(v, 4));
}

输入

[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]]
4

输出

2

Arnab Chakraborty

更新于: 2020-04-30

165 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习