最大的以 1 为边界的正方形

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

示例 1：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/largest-1-bordered-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、预处理数组

left:每一行中的每一列从左到右连续为1的最长长度
top:每一列中的每一行从下到上连续为1的最长长度

        int n=grid.length;
        int m=grid[0].length;
        int[][] right=new int[n][m];
        int[][] top=new int[n][m];
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(j==m-1&&grid[i][j]==1){
                    right[i][j]=1;
                }else if(j!=m-1&&grid[i][j]==1){
                    right[i][j]=right[i][j+1]+1;
                }else{
                    right[i][j]=0;
                }
            }
        }
        
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(j==n-1&&grid[j][i]==1){
                    top[j][i]=1;
                }else if(j!=n-1&&grid[j][i]==1){
                    top[j][i]=top[j+1][i]+1;
                }
            }
        }

二、解题步骤

有了预处理数组后,我们就可以轻松解题了
我们知道任何一个(i,j)位置右边有多少个连续的1,下方有多少个连续的1(包括自己在内)
同时,我们也可以知道(i+size,j)右边位置有多少个连续的1
和(i,j+size)下方位置有多少个连续的1;
如果这4条边连续的1的数量相等,则为一个正方形
我们从最大边开始找

代码

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
        int[][] right=new int[n][m];
        int[][] top=new int[n][m];
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(j==m-1&&grid[i][j]==1){
                    right[i][j]=1;
                }else if(j!=m-1&&grid[i][j]==1){
                    right[i][j]=right[i][j+1]+1;
                }else{
                    right[i][j]=0;
                }
            }
        }
        
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(j==n-1&&grid[j][i]==1){
                    top[j][i]=1;
                }else if(j!=n-1&&grid[j][i]==1){
                    top[j][i]=top[j+1][i]+1;
                }
            }
        }
        
        for(int size=Math.min(n,m);size!=0;size--){
            if(isSquare(size,right,top)){
                return size*size;
            }
        }
        return 0;
    }
    public boolean isSquare(int size,int[][] right,int[][] top){
        for(int i=0;i!=right.length-size+1;i++){
            for(int j=0;j!=top[0].length-size+1;j++){
                if(right[i][j]>=size&&top[i][j]>=size&&right[i+size-1][j]>=size&&top[i][j+size-1]>=size){
                    return true;
                }
            }
        }
        return false;
    }
}