目标
给你一个大小为 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
思路
有一个 m x n 矩阵，返回其中元素和不超过 threshold 的正方形的最大边长。
使用二维前缀和计算面积，枚举右下顶点与边长，边长从已知的最大值开始枚举，超出 threshold 就退出循环，时间复杂度为 O(mn + min(m, n))。
代码
/**
* @date 2026-01-19 9:46
*/
public class MaxSideLength1292 {
public int maxSideLength_v1(int[][] mat, int threshold) {
int m = mat.length;
int n = mat[0].length;
int[][] prefix = new int[m + 1][n + 1];
int res = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = prefix[i][j - 1] + mat[i - 1][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
int l = Math.min(i, j);
for (int k = res + 1; k <= l; k++) {
int area = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k];
if (area <= threshold) {
res = Math.max(res, k);
} else {
break;
}
}
}
}
return res;
}
}
性能
