LC-1139.最大的以1为边界的正方形

题目描述

leetcode 中等题

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

示例1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

提示1：

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为 0 或 1

前缀和/动态规划

容易想到，我们可以枚举所有点 $g[i][j]$ 作为正方形的左上顶点时，所能取到的最大边长是多少，取所有点所取的最大边长再开方，即为答案。

我们可以尝试枚举所有点、所有可能的边长，此时最多约有 $100 \times 100 \times 100 = 10^6$ 次运算，所以对于判断某个正方形是否满足题目条件，需要在较短最好是 $O(1)$ 的时间内做到。

我们如果能预处理出以每个顶点向右最多有几个 $1$ ，向下最多有几个 $1$ ，设其分别为 $right[i][j]、down[i][j]$ ，就能在 $O(1)$ 的时间内判断出以 $g[i][j]$ 作为左上端点、以 $k$ 作为边长的正方形是否满足条件，显然此时当 $right[i][j] >= k　and　down[i][j] >= k　and　right[i + k][j] >= k　and　down[i][j + k] >= k$ 时，该正方形合法。

对于 $right、down$ 数组的维护，可以从两个角度理解。一是前缀和，两个数组分别为不同方向的前缀和，只需要处理好遍历顺序即可；二是动态规划，以 $right$ 为例，显然有以下转移方程：
$$
\begin{align}
&right[i][j] = 0　　　　　　　　　　　　　　　　　　　 g[i][j] == 0\\
&right[i][j] = right[i][j + 1] + 1　　　　　　　　　　　g[i][j] == 1 \\
\end{align}
$$

class Solution {
    public int largest1BorderedSquare(int[][] g) {
        int n = g.length, m = g[0].length;
        int[][] right = new int[n + 1][m + 1], down = new int[n + 1][m + 1];
        for(int i = n - 1; i >= 0; i--){
            for(int j = m - 1; j >= 0; j--){
                if(g[i][j] == 1){
                    right[i][j] = right[i][j+ 1] + 1;
                    down[i][j] = down[i + 1][j] + 1;
                }
            }
        }
        int maxLength = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                for(int k = Math.max(0, maxLength - 1); right[i][j] >= k + 1 && down[i][j] >= k + 1 && k + j < m && k + i < n; k++){
                    if(right[i + k][j] >= k + 1 && down[i][j + k] >= k + 1){
                        maxLength = Math.max(maxLength, k + 1);
                    }
                }
            }
        }
        return maxLength * maxLength;
    }
}