1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length, n = mat[0].length;
int maxSideLength = 0;
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
mat[i][j] += mat[i][j - 1];
}
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
mat[i][j] += mat[i - 1][j];
}
}
int sideLength = Math.min(m, n);
while (sideLength > 0) {
for (int i = sideLength - 1; i < m; i++) {
for (int j = sideLength-1; j <n ; j++) {
int a = i - sideLength >= 0 && j - sideLength >= 0 ? mat[i - sideLength][j - sideLength] : 0;
int b = i - sideLength >= 0 ? mat[i - sideLength][j] : 0;
int c = j - sideLength >= 0 ? mat[i][j - sideLength] : 0;
int d = mat[i][j];
int sum = d - b - c + a;
if (sum <= threshold) {
return sideLength;
}
}
}
sideLength--;
}
return maxSideLength;
}
}
|
References
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold