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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33