网络知识 娱乐 LeetCode 1139. 最大的以 1 为边界的正方形

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

截止到目前我已经写了 600多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

在这里插入图片描述
前面我们讲过《530,动态规划解最大正方形》。第530题需要正方形所有网格中的数字都是1,只要搞懂动态规划的原理,代码就非常简洁。而这题只要正方形4条边的网格都是1即可,中间是什么数字不用管,相对来说这题难度要比第530题稍微大一些。

这题解题思路是这样的

  • 第一步先计算每个网格中横向和竖向连续1的个数。
  • 第二步遍历二维网格,以每一个格子为正方形的右下角,分别找出上边和左边连续1的个数,取最小值作为正方形的边长,然后判断正方形的左边和上边长度是否都大于等于正方形边长,如果都大于等于正方形边长就更新正方形的最大边长,否则缩小正方形的边长,继续判断……。

如果看不懂也没关系,我们一步一步来,等分析完之后回过头来看,你会恍然大悟,原来这么简单。

1,第一步,计算横向和竖向连续1的个数,举个例子。

在这里插入图片描述
代码比较简单,我们定义一个三维数组,其中

  • dp[i][j][0]: (i,j)横向连续1的个数
  • dp[i][j][1]: (i,j)竖向连续1的个数

我们计算的时候,如果当前位置是0就跳过,只有是1的时候才计算,分别统计左边和上边(也就是横向和竖向)连续1的个数。代码比较简单,我们来看下(这里为了减少一些边界条件的判断,把dp的宽和高都增加了1)。

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++) {
        //如果当前位置是0,就跳过
        if (grid[i - 1][j - 1] == 0)
            continue;
        //如果是1,我们就计算横向和竖向连续1的个数
        dp[i][j][0] = dp[i][j - 1][0] + 1;
        dp[i][j][1] = dp[i - 1][j][1] + 1;
    }
}

2,第二步,找出正方形的最大边长

我们会以网格中的每一个位置为正方形的右下角,来找出正方形的边长。如下图所示,我们以橙色的位置1为正方形的右下角,分别沿着左边和上边找出他们连续1的个数,最小的作为正方形的边长。因为左边和上边连续1的个数我们在第一步的时候已经计算过,分别是dp[i][j][0]和dp[i][j][1],也就是正方形的边长我们暂时可以认为是,

int curSide = Math.min(dp[i][j][0], dp[i][j][1]);

在这里插入图片描述
其实大家已经看到了这个边长就是正方形下边和右边的长度,但是正方形的上边和左边我们还没确定,我们继续确定正方形左边和上边的长度。会有两种情况

一种如下图所示,就是正方形左边和上边的长度都大于curSide,我们可以认为以坐标(i,j)为右下角的正方形的最大长度就是curSide

在这里插入图片描述

另一种如下图所示,正方形上边的长度是1,小于curSide

在这里插入图片描述

这种情况下是构不成正方形的,所以我们要缩小curSide的值,然后再继续判断……

搞懂了上面的过程,代码就简单多了,我们来直接看下代码。

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++) {
            //如果当前位置是0,就跳过
            if (grid[i - 1][j - 1] == 0)
                continue;
            //如果是1,我们就计算横向和竖向连续1的个数
            dp[i][j][0] = dp[i][j - 1][0] + 1;
            dp[i][j][1] = dp[i - 1][j][1] + 1;
        }
    }
    int maxSide = 0;//记录正方形的最大长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //沿着当前坐标往上和往左找出最短的距离,暂时看做是正方形的边长(正方形的具体边长
            //还要看上边和左边的长度,所以这里要判断一下)
            int curSide = Math.min(dp[i][j][0], dp[i][j][1]);
            //如果边长小于maxSide,即使找到了也不可能再比maxSide大,所以我们没必要再找,直接跳过,
            if (curSide <= maxSide)
                continue;
            //curSide可以认为是正方形下边和右边的长度,我们还需要根据正方形上边和左边的长度
            //来确认是否满足正方形的条件
            for (; curSide > maxSide; curSide--) {
                //判断正方形的左边和上边的长度是否大于curSide,如果不大于,我们就缩小正方形
                //的长度curSide,然后继续判断
                if (dp[i][j - curSide + 1][1] >= curSide && dp[i - curSide + 1][j][0] >= curSide) {
                    maxSide = curSide;
                    //更短的就没必要考虑了,这里直接中断
                    break;
                }
            }
        }
    }
    //返回正方形的边长
    return maxSide * maxSide;
}

时间复杂度:O(m*n*min(m,n)),m和n分别是矩阵的宽和高
空间复杂度:O(m*n),使用了一个三维数组(m*n*2)