题目：
给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
示例 1：
输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：9
示例 2：
输入：grid = [[1,1,0,0]] 输出：1
这一题与算法48有点相似，但是它不能用单调栈解决这个问题。也不能用算法48的动态规划思想来解决。因为这一题是以全部为1的边组成的最大面积。也就是说中间是可以为0的。式例1就是最好的说明。
上一题用了单调栈、动态规划、暴力解。而这一题已经把前两种可能性已经排除掉了。只剩下暴力解了。那么，暴力解如何来解决这一题呢？
1. 正方形有4个顶点、4条边。只要验证每条边是否全部为1就可以了
2. 每增加一行一列，就验证新增的这些边是否全部为1就可以。如果验证不通过，没关系，继续往后验证。因为，当前新增的边并不一定就是最终的正方形边长，如果它只是最大正方形内部的一些元素而已，那我们根本不关注它是否为0.
3. 需要注意的是，正方形的上方边和左方边出现了0， 那就不能继续去判断了。因为一点正方形的左上方顶点一旦确定，那上方边长和左方边长就已经确定了延长的方向了。但是，右侧的边和下方的边是要全部遍历完，才能最后确定的。
package code04.动态规划专项训练02;
/**
* 力扣 1139 最大的以1为边界的正方形
* https://leetcode.com/problems/largest-1-bordered-square/
*/
public class Largest1BorderedSquare_04_leetcode1139暴力解 {
public int largest1BorderedSquare( int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int row = matrix.length;
int col = matrix[0].length;
//全局正方形最大边长
int maxSide = 0;
for (int i = 0; i < row ; i++) {
//当前行的每一列都作为正方形的左上角，即起始点
for (int j = 0; j < col; j++) {
//当前格子是否为1,为1才可能成为正方形的起始点
if (matrix[i][j] == 0) {
continue;
}
//整个二维数组中，重要有1出现，那正方形边长至少为1
if (maxSide == 0) {
maxSide = 1;
}
//行边长，列边长，两者取小。因为是正方形
int p = Math.min(row - i, col - j);
//当前单元格 matrix[i][j] 开始的最大正方形边长
int tempMaxSide = 1;
boolean flag = true;
//从i,j开始 到 i+index,j+index 范围内。全部都为1，才能验证通过
//start为默认边长，默认边长为1. 因为matrix[i][j] == 1
for (int count = 1; count < p; count++) {
//上方边长 matrix[i][j+count] == '0'
//左方边长 matrix[i + count][j] == '0'
if (matrix[i][j+count] == 0
|| matrix[i + count][j] == 0) {
break;
}
int addCol = j + count;
int addRow = i + count;
//新增的行和列，不是全部范围
for (int m = 1; m <= count; m++) {
//下方边长 matrix[addRow][j + m]
//右方边长 matrix[i + m][addCol] == '0'
if (matrix[addRow][j + m] == 0
|| matrix[i + m][addCol] == 0) {
flag = false;
}
}
if (flag) {
tempMaxSide = Math.max(tempMaxSide, count + 1);
}
else {
//即使右边长、下方边长遇到0. 继续放行验证。
//因为当前边长有可能不是最终正方形的边界
flag = true;
}
}
/**
* 以当前单元格 matrix[i][j] 边长扩展完毕，
* tempMaxSide 以matrix[i][j] 为正方形左上顶点的最大边长为
* maxSide 整个区域之前最大正方形边长为
*/
maxSide = Math.max(maxSide, tempMaxSide);
}
}
return maxSide * maxSide;
}
public static void main(String[] args) {
Largest1BorderedSquare_04_leetcode1139暴力解 ss = new Largest1BorderedSquare_04_leetcode1139暴力解();
//int[][] matrix = {{1,1,1}, {1,0,1},{1,1,1}};
int[][] matrix = {{1,1,1}, {1,1,0},{1,1,1},{0,1,1},{1,1,1}};
System.out.println(ss.largest1BorderedSquare(matrix));
}
}
虽然只是暴力解，但是它只花费了5毫秒，胜率86%，已经相当的nice了。
那么，这一题是否有动态规划解法呢，答案是有。
下面来说一下动态规划的思路，以事例1为案例进行分析。
原始数组：
| 下标 0 | 下标 1 | 下标 2 | |
| 下标 0 | 1 | 1 | 1 |
| 下标 1 | 1 | 0 | 1 |
| 下标 2 | 1 | 1 | 1 |
由下往上，推算每个单元格距离底部的距离。遇到1就累加，遇到0就是0.
每个单元格下方1的数量：
| 下标 0 | 下标 1 | 下标 2 | |
| 下标 0 | 3 | 1 | 3 |
| 下标 1 | 2 | 0 | 2 |
| 下标 2 | 1 | 1 | 1 |
从右往左，推算出每个单元格右侧1的数量：
| 下标 0 | 下标 1 | 下标 2 | |
| 下标 0 | 3 | 2 | 1 |
| 下标 1 | 1 | 0 | 1 |
| 下标 2 | 3 | 2 | 1 |
1. 原始数组的0行0列为1，那么右侧有3个1， 下方也有3个1. 正方形的边长必须相等，因此两者取小。 也就是说，如果以原始数组0行0列为正方形的左顶点，那么这个正方形的最大边长肯定是小于等于3的。
2. 然后就是遍历了。最大长度为1，为2，为3，逐步验证。最终确定，最大正方形的的边长，到底是多少。
3. 在步骤1讨论的过程中，我们依旧确定了正方形上方边、左侧边的边长了。那么，下方的边、右侧的边也需要验证的。下方的边，可以通过左下方的顶点右侧1的数量来确定，必须大于步骤2讨论的边长。右侧的边可以通过正方形右上方的顶点来确定，右上方的顶点下方1的数量大于等于步骤2讨论的边长即可。
动态规划代码：
package code04.动态规划专项训练02;
/**
* 力扣 1139 最大的以1为边界的正方形
* https://leetcode.com/problems/largest-1-bordered-square/
*/
public class Largest1BorderedSquare_04_leetcode1139动态规划 {
//统计每个单元格，右侧连续有几个1；下方连续有几个1；
public void preHandle(int[][] matrix, int[][] rightArr, int[][] bottomArr)
{
int rowLength = matrix.length;
int colLength = matrix[0].length;
bottomArr[rowLength-1][colLength-1] = matrix[rowLength-1][colLength-1];
rightArr[rowLength-1][colLength-1] = matrix[rowLength-1][colLength-1];
//最后一行.
for (int i = colLength - 2; i >= 0; i--) {
//距离底部有几个1
bottomArr[rowLength - 1][i] = matrix[rowLength - 1][i];
//距离右侧有几个1
rightArr[rowLength - 1][i] = matrix[rowLength - 1][i] == 0 ? 0 : matrix[rowLength - 1][i] + rightArr[rowLength - 1][i + 1];
}
//最后一列
for (int i = matrix.length - 2; i >= 0; i--) {
//距离底部有几个1
bottomArr[i][colLength - 1] = matrix[i][colLength - 1] == 0 ? 0 : matrix[i][colLength - 1] + bottomArr[i + 1][colLength - 1];
//距离右侧有几个1
rightArr[i][colLength - 1] = matrix[i][colLength - 1];
}
for (int i = matrix.length -2; i >= 0; i--) {
for (int j = matrix[0].length - 2; j >= 0; j--) {
if (matrix[i][j] == 1) {
bottomArr[i][j] = matrix[i][j] + bottomArr[i+1][j];
rightArr[i][j] = matrix[i][j] + rightArr[i][j + 1];
}
}
}
}
public int largest1BorderedSquare(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int row = matrix.length;
int col = matrix[0].length;
int[][] rightArr = new int[row][col];
int[][] bottomArr = new int[row][col];
//预处理数组
preHandle(matrix, rightArr, bottomArr);
//全局正方形最大边长
int maxSide = 0;
for (int i = 0; i < row ; i++) {
//当前行的每一列都作为正方形的左上角，即起始点
for (int j = 0; j < col; j++) {
//当前格子是否为1,为1才可能成为正方形的起始点
if (matrix[i][j] == 0) {
continue;
}
//整个二维数组中，重要有1出现，那正方形边长至少为1
if (maxSide == 0) {
maxSide = 1;
}
//行边长，列边长，两者取小。因为是正方形
int sideLength = Math.min(rightArr[i][j], bottomArr[i][j]);
boolean flag = true;
for (int m = 1; m < sideLength; m++) {
//正方形的右上顶点往下数，即右边边长
int rightLength = bottomArr[i][j + m];
//正方形的底部边长
int bottomLength = rightArr[i + m][j];
//当前边长
int length = m + 1;
if (rightLength >= length && bottomLength >= length) {
maxSide = Math.max(maxSide, length);
}
}
}
}
return maxSide * maxSide;
}
public static void main(String[] args) {
Largest1BorderedSquare_04_leetcode1139动态规划 ss = new Largest1BorderedSquare_04_leetcode1139动态规划();
//int[][] matrix = {{1,1,1}, {1,0,1},{1,1,1}};
int[][] matrix = {{1,1,1}, {1,1,0},{1,1,1},{0,1,1},{1,1,1}};
System.out.println(ss.largest1BorderedSquare(matrix));
}
}
7毫秒，50%的胜率，也还可以了。
虽然这一题也有动态规划，但是，它是基于暴力解逐步演化过来的。暴力解法时间复杂度为 O（N^4）。我们基于暴力解在讨论边长的过程中还需要一次遍历，通过数组预处理的的方式提前进行了统计，简化了验证新增列的验证。因此，动态规划的时间复杂度为 O(N^3) + O(N^2). 实际就是O(N^3)。
这一道题，动态规划的性能比暴力解的还要低一些，虽然动态规划的时间复杂度为O(N^3)，而暴力解的时间复杂度为O(N^4)。
动态规划的时间复杂度为O(N^3)，但是，它还有一个O(N^2)预处理数组的过程。因为力扣数据量有限，动态规划时间复杂度虽然降低了一阶，但是直观看起来还是没有暴力解高。
随着数据量的增大，动态规划还是要优于暴力解的。
