题目： 给你一个由若干 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
题目来源：力扣（LeetCode） https://leetcode-cn.com/problems/largest-1-bordered-square
参考大佬的代码 1、判断是最大正方形，就是判断正方形的四条边是否上的每个元素都为1，并且在所有正方形子网络中是最大的。
2、从左到右、从上到下遍历每个元素，如果该元素为 1 ，将该元素点作为正方形子网络中的一个顶点，在这里作为正方形右下角的顶点（rd），这样只需考虑左、上方的元素，即当遍历到该元素时，寻找以该元素作为右下角顶点的最大正方形。
3、如何搜索该顶点的最大正方形。我们需要得到该顶点左边 rd_left 连续为 1 的元素个数（包括自身） ，得到该顶点上边 rd_above 连续为 1 的元素个数，以这个数中的小者 min 作为可能最大正方形的边，这样就得到可能正方形的下边和右边，此时还需要判断可能正方形的上边和左边。根据 rd 与 min 可以得到可能正方形左下角顶点 ld 与右上角顶点 ra。根据这两个顶点得到 ld_above 与 ra_left，判断这两个数是否比 min 大，是，则得到以该元素为右下角顶点的最大正方形；否则，将 min 减 1 ，即减小正方形四个边 1，重新获取左下角与右上角的顶点并判断。依次遍历二维数组中的所有点，重复上面的操作。
由于每次遍历到每个为 1 的元素并寻找对应的最大正方形时，都需要以往遍历过元素的相关数据，即重复访问某些子问题，所有这里采用动态规划，保存遍历过的元素信息。
代码：
public int largest1BorderedSquare(int[][] grid) { // 如果为长度为零，则返回0； if(grid.length == 0){ return 0; } // 设初始最大正方形的边的 1 的个数为 num = 0。 // 按照从左到右、从上到下依次遍历二维数组中的每个元素，并且以当前元素为正方形的右下顶点 rd。 // 判断元素左边 rd_left（包括自身）有多少个连续的 1 ，判断元素上边 rd_above 有多少个连续的 1 。 // 比较 rd_left 与 rd_above 的大小，选取小的 min 作为可能构成的最大的正方形。 // 判断正方形左下顶点 ld 的上边 ld_above 元素连续的为 1 的个数，判断正方行右上顶点 ra 的左边 ra_left 元素连续的为 1 的个数。 // 若都为 min ，则保存该正方形边的 1 的个数到 num。 // 若采用递归，每次遍历到某个元素都要从新去计算一个元素及的左上 1 的个数，这样重复的计算就很多 // 所以这里采用动态规划，设计一个三位数组 dp[row][col][2]用来保存每个元素点的左上连续为 1 的个数。这样每次只需查找即可。 int num = 0; int min = 0; // 保存每个元素左上连续为 1 的个数。 0 代表左边，1 代表上边，比数组长度多1是为了方便循环计算。 int[][][] dp = new int[grid.length + 1][grid[0].length + 1][2]; // 遍历行 for (int i = 1; i <=grid.length; i++) { // 遍历列 for (int j = 1; j <=grid[0].length; j++) { // 如果当前元素为 1 ，dp记录其左、上元素连续为 1 的个数。否则计为0 if (grid[i-1][j-1] == 1){ dp[i][j][0] = dp[i][j-1][0] + 1; dp[i][j][1] = dp[i-1][j][1] + 1; // 得到左、上中的小者 min = (dp[i][j][0]<=dp[i][j][1]) ? dp[i][j][0] : dp[i][j][1]; // 左下、右上顶点对应的上边、左边连续 1 的个数 while (dp[i][j-min+1][1]<min || dp[i-min+1][j][0]<min){ min--; } num = (num>=min) ? num : min; } } } return num*num; }欢迎大家一起交流。
