原文链接: https://leetcode-cn.com/problems/largest-1-bordered-square

英文原文

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

 

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

 

Constraints:

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 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

通过代码

高赞题解

思路

首先定义DP数组

dp[i][j][0]: i,j左边连续的1的个数（包括自身）
dp[i][j][1]: i,j上边连续的1的个数（包括自身）

然后递推预处理这一部分

[]
int[][][] dp = new int[m+1][n+1][2];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (grid[i-1][j-1] == 1){
            dp[i][j][0] = 1 + dp[i][j-1][0];
            dp[i][j][1] = 1 + dp[i-1][j][1];
        }
    }
}

简单画了个图（和实际代码有一点出入，实际代码为了方便初始化，dp[i][j]代表的其实是grid[i-1][j-1]）

求以某个点为右下角的正方形，首先我们考虑这个点为右下角可能构成的最大正方形边长是多大

很明显应该是该点左边和上边连续1个数的最小值，如上图的（6，5）点，最大的可能边长就应该是6，然后我们枚举所有的小于等于6大于等于1的边长side，验证side能否构成正方形

验证side是否合法也很容易，如上图，我们只需要考虑（6，5）上边距离为side的点的左边连续1的个数是否大于等于side（dp[i-side+1][j][0] >= side），以及左边距离为side的点的上边连续的1的个数是否大于等于side（dp[i][j-side+1][1] >= side），如果都大于等于side那么该side就是合法的，我们统计这些合法的side的最大值就ok了

Code

[]
public int largest1BorderedSquare(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    //dp[i][j][0]: i,j左边连续的1的个数
    //dp[i][j][1]: i,j上边连续的1的个数
    int[][][] dp = new int[m+1][n+1][2];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (grid[i-1][j-1] == 1){
                dp[i][j][0] = 1 + dp[i][j-1][0];
                dp[i][j][1] = 1 + dp[i-1][j][1];
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //最短的那条边不一定是合法的边长，如果该边长不合法就需要缩减边长，直到找到合法的
            for (int side = Math.min(dp[i][j][0], dp[i][j][1]); side >= 1; side--){
                if (dp[i][j-side+1][1] >= side && dp[i-side+1][j][0] >= side){
                    res = Math.max(res, side);
                    break; //更短的就没必要考虑了
                }
            }
        }
    }
    return res * res;
}

统计信息

通过次数	提交次数	AC比率
9744	20310	48.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言