[每日一题]1139.最大的以1为边界的正方形
1139. 最大的以 1 为边界的正方形 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：9
输入：grid = [[1,1,0,0]] 输出：1
Solution
class Solution {
public int largest1BorderedSquare(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] right = new int[m + 1][n + 1]; // 右边有多少连续的1
int[][] down = new int[m + 1][n + 1]; // 下边有多少连续的1
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] != 0) {
down[i][j] = 1 + down[i + 1][j];
right[i][j] = 1 + right[i][j + 1];
}
}
}
int res = 0;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int start = Math.max(res, 1);
int end = Math.min(down[i][j], right[i][j]);
// 判断右上角的down
// 判断左下角的right
for (int k = end; k >= start; k--) {
int ru = j + k - 1;
int ld = i + k - 1;
if (down[i][ru] >= k && right[ld][j] >= k) {
res = k;
break;
}
}
}
}
return res * res;
}
}