LeetCode每日一题（2023/2/17）

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

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

示例 1：

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

输入：grid = [[1,1,0,0]]
输出：1
 
提示：

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

解答：二维前缀和+三层循环

class Solution {
    int[][] s;//前缀和数组
    public int largest1BorderedSquare(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        s=new int[m+1][n+1];
          for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    //二位前缀和
                     s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+grid[i-1][j-1];
                }    
            }
        for(int len=Math.min(m,n);len>1;len--){
            for(int i=1;i+len-1<=m;i++){
                for(int j=1;j+len-1<=n;j++){
                    int a=i,b=j,c=i+len-1,d=j+len-1;
                    //通过二维前缀和计算周长
                    //get(a,b,c,d)-get(a+1,b+1,c-1,d-1)
                    if((len-1)*4==get(a,b,c,d)-get(a+1,b+1,c-1,d-1))
                        return len*len;
                }    
            }
        }
        //特判长度为1的时候
        if(s[m][n]>0)return 1;
        return  0;
    }
    //计算(x1,y1)为左上端点和(x2,y2)为右下端点的矩形前缀和
    int get(int x1,int y1,int x2,int y2){
        return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
    }
}