The rest of the world may follow the rules, but I must follow my heart.

世人也许循规蹈矩，但我必须遵从内心。

问题描述

来源：LeetCode第1139题

难度：中等

给你一个由若干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

问题分析

前面我们讲过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）。


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的值，然后再继续判断……

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

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


本文原创，未经作者允许不可转载！
更多内容，欢迎关注作者微信公众号：数据结构和算法！