# 最大正方形

​ 大一 -> 大二暑期算法作业

​ 分站已经上线简约风算法作业集合（也可以选择阅读模式

# 看到题目的感想

​ 寻找最大正方形是小时候经常玩的一种游戏，说是可以锻炼观察力与判断力什么的，现在也会有家长带着小孩玩这个游戏，不过不是很多。

# 题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 题目解答

​ （**ps：** 由于做题时采用的是执行代码，并未提交，提交结果均为后来补上，所以时间均为两天前）

# 1、暴力计算

# （1）解题思路

语言描述不是很棒，大家凑活看叭，┭┮﹏┭┮

想了想，暴力计算是最简单直观的做法，具体做法如下：

  1. 遍历矩阵中的元素，当遇到 1 时，将该元素作为正方形的左上角的位置。
  2. 确定正方形的左上角后，根据左上角所在的行和列计算可能的最大正方形的边长（正方形的范围 - 不能超出矩阵的行和列），在该范围内寻找只包含 1 的最大正方形；
  3. 每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1。（方便起见，需要先判断选取的点的右下角的点是否为 1。若不是，则跳出本次循环并储存当前的最大正方形，找到下一个元素是 1 的节点作为左上角点，重复 2、3 步；若是，则判断下一行和右一列的其他元素是否都为 1 （注：这里不是下一行右一列的所有元素，而是初始左上角和以当前点为右下角的正方形的范围内的点，如下图） ，若不都为 1，则跳出本次循环并储存当前的最大正方形，找到下一个元素是 1 的节点作为左上角点，重复 2、3 步；若都为 1，则继续第 3 步）。

# （2）代码

配合题目链接食用

# java
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
34
35
36
class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { // 没有矩阵或矩阵大小为0时
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') { // 遇到一个 1 作为正方形的左上角
                    maxSide = Math.max(maxSide, 1); // 更新可能的最大正方形边长
                    int currentMaxSide = Math.min(rows - i, columns - j); // 当前最大正方形边长
                    for (int k = 1; k < currentMaxSide; k++) { // 判断新增的一行一列是否均为 1
                        boolean flag = true;
                        if (matrix[i + k][j + k] == '0') { // 判断右下角的点
                            break;
                        }
                        for (int m = 0; m < k; m++) { // 判断下一行右一列
                            if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) { // 若判断都是1，则更新，不是则退出本次循环，寻找下一个左上角
                            maxSide = Math.max(maxSide, k + 1); // 更新可能的最大正方形边长
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}

image-20210827093335340.png

# （3）总结

​ 暴力的思路比其他方法简单（但是我的描述可能会有些不顺畅），但是效率不高。

# 2、dp 算法（动态规划）（来自题解）

​ 又一次见到了动态规划，还是有无从下手的感觉。

# （1）解题思路

​ 方法一虽然直观，但是时间复杂度太高，有没有办法降低时间复杂度呢？

可以使用动态规划降低时间复杂度。我们用 dp (i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp (i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。

那么如何计算 dp 中的每个元素值呢？对于每个位置 (i,j)，检查在矩阵中该位置的值：

  • 如果该位置的值是 0，则 dp (i,j)=0，因为当前位置不可能在由 1 组成的正方形中；

  • 如果该位置的值是 11，则 dp (i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

    ​ dp(i,j) = min( dp(i−1,j) , dp(i−1,j−1) , dp(i,j−1) ) + 1

    如果读者对这个状态转移方程感到不解，可以参考 1277. 统计全为 1 的正方形子矩阵的官方题解，其中给出了详细的证明。

此外，还需要考虑边界条件。如果 i 和 j 中至少有一个为 0，则以位置 (i, j)(i,j) 为右下角的最大正方形的边长只能是 11，因此 dp (i,j)=1。

以下用一个例子具体说明。原始矩阵如下。

0 1 1 1 0
1 1 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 1 1
对应的 dp 值如下。

0 1 1 1 0
1 1 2 2 0
0 1 2 3 1
0 1 2 3 2
0 0 1 2 3

下图也给出了计算 dp 值的过程。

# （2）代码

配合题目链接食用

# Java
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
class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# C++
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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        int maxSide = 0;
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(columns));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# （3）总结

​ 动态规划解题的思想还需要学习，现在还上不了手。

# 题目总结

​ 这次的题目是数最大正方形，暴力方法还是最先考虑到的，之后菜知道动态规划也可以解决。（动态规划现在还属实不会）