leetcode 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

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 10^4
• 0 <= threshold <= 10^5

分析：预处理出二维前缀和数组 pre_sum，其中 pre_sum[i][j] 代表坐标 (i,j) 自身以及它下方、右方所有元素的和。之后枚举正方形边长，检查是否存在元素和小于 threshold 的情况。

int maxSideLength(int** mat, int matSize, int* matColSize, int threshold) { int n=matSize,m=matColSize[0]; int pre_sum[n+5][m+5]; for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) pre_sum[i][j]=0; pre_sum[n-1][m-1]=mat[n-1][m-1]; for(int j=m-2;j>=0;--j) pre_sum[n-1][j]=mat[n-1][j]+pre_sum[n-1][j+1]; for(int i=n-2;i>=0;--i) pre_sum[i][m-1]=mat[i][m-1]+pre_sum[i+1][m-1]; for(int i=n-2;i>=0;--i) for(int j=m-2;j>=0;--j) pre_sum[i][j]=mat[i][j]+pre_sum[i+1][j]+pre_sum[i][j+1]-pre_sum[i+1][j+1]; int maxn=n>=m?m:n,ans=0; for(int l=0;l<=maxn;++l) { int f=0; for(int i=0;i<n-l&&!f;i++) { int sum=0; for(int j=0;j<m-l&&!f;++j) { sum=pre_sum[i][j]-pre_sum[i+l+1][j]-pre_sum[i][j+l+1]+pre_sum[i+l+1][j+l+1]; if(sum<=threshold) f=1; } } if(!f)break; ans=l+1; } return ans; }