A.每日一题——1292. 元素和小于等于阈值的正方形的最大边长

题目链接：1292. 元素和小于等于阈值的正方形的最大边长（中等）

算法原理：

解法：暴力枚举

5ms击败98.26%

时间复杂度O(mn min(m,n))

预处理二维前缀和之后，先来两层循环，枚举正方形的左上角( i , j )，内层循环枚举正方形的边长，直至出界或者正方形元素和>threshold 为止，在此过程中逐步更新 ret 的最大值

Java代码：

class Solution { public int maxSideLength(int[][] mat, int threshold) { int m=mat.length,n=mat[0].length; int[][] sum=new int[m+1][n+1]; //初始化二维前缀和数组 for(int i=0;i<m;i++) for(int j=0;j<n;j++) sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[i][j]+mat[i][j]; int ret=0; //遍历原矩阵每个位置作为正方形的左上角(i,j) for(int i=0;i<m;i++) for(int j=0;j<n;j++) while(i+ret<m&&j+ret<n&&query(sum,i,j,i+ret,j+ret)<=threshold) ret++;//满足条件，边长+1，继续尝试更大边长 return ret; } //返回左上角在(r1,c1)，右下角在(r2,c2)的子矩阵元素和 private int query(int[][] sum,int r1,int c1,int r2,int c2){ return sum[r2+1][c2+1]-sum[r2+1][c1]-sum[r1][c2+1]+sum[r1][c1]; } }