算法题： 221. 最大正方形

正方形"/>

算法题： 221. 最大正方形

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1

输入：matrix = [[“0”]]
输出：0

来源：力扣（LeetCode）

结果

执行用时：5 ms, 在所有 Java 提交中击败了94.68%的用户

内存消耗：52.7 MB, 在所有 Java 提交中击败了71.23%的用户

通过测试用例：77 / 77

题解

图解

本题目意思就是判断由一组成的最大正方形的面积

已经分析出现大量的重复计算，非常耗费时间与内存，所以我们可以想到使用动态规划法

所谓动态规划法没有想的那么难，本人面对套路编程，将最复杂的知识就简单的讲解给大家

动态规划在我开来大体上分三步

第一步：确定数组

结果一般就是数组

创建数组（大部分情况下是二维的），我们自己可以看出来比如像什么方格什么的一看就是数组

我们需要什么，结果是什么数组的最大坐标数字一般就是什么

提供的条件为m,n的二维数组，我们就可以创建数组dp[][]，则结果就是dp[m-1][n-1]

但是此题非常的坑，一共由两点

一、我们所求的结果根本就不可能是我们想要结果，只能得到边长，面积是无法得到的

二、得到的最终也只能代表最终坐标，所以我们还要取判断一个dp数组中最大的元素值

第二步：寻找关系，普遍的推导规矩

我们可以发现所需要的正方形必须为字符1构成的，所以我们应该会考到，如果为零的字符，拿根本不用看了，肯定是无法构成需要的正方形，所以长度直接为0就可以了，我们发现我们只要查看（拿第一元素为例子：dp[0][0]），只需要查看元素的下、右、右下元素就ok了，但是把这样对我们来说书写起来到结束，也即是n-1再判断，周围缺少元素的情况，我们难免会有一些不舒服，所以我们一个让元素当正方形的右下角元素，这样我们就很容易的处理周围缺少元素的情况，直接用【0】【i】+for循环就可以解决，第一行特殊问题处理完毕，第一列处理方法类似，

我们本身为1但是周围有含有0的那我们的长度就为1

而如果我们周围是全是1的情况下，可以有的边长2，有的为1，而如果三个方向存在的边长如果不相等的情况下，那我们一定取最小的，再加上我们本身的长度

即为：dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1

第三步：处理特殊情况

我们遇到的特殊情况就是，如果我们的三个方向缺少元素（第一行，第一列），我们就不需要看三个方向的值，只需要看他们自身就可以了，如果符合长度为1，不符合长度为0。

如果还是不理解可以自己画图，一定要画图，如果能看出了你就是图灵奖获得者了，铁铁

代码如下：

public int maximalSquare(char[][] matrix) {int max = 0;int[][] dp = new int[matrix.length][matrix[0].length];for (int i = 0; i < matrix[0].length; i++) {if (matrix[0][i] == '0') {dp[0][i] = 0;} else {dp[0][i] = 1;max=1;}}for (int i = 0; i < matrix.length; i++) {if (matrix[i][0] == '0') {dp[i][0] = 0;} else {dp[i][0] = 1;max=1;}}for (int i = 1; i < matrix.length; i++) {for (int j = 1; j < matrix[i].length; j++) {if (matrix[i][j] == '0') {dp[i][j] = 0;} else {dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]))+1;if (max < dp[i][j]) {max = dp[i][j];}}}}return max * max;
}