题解 | #最大正方形#

由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。
暴力法是最简单直观的做法，具体做法如下：
1、遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角；
2、确定正方形的左上角后，根据左上角所在的行和列计算可能的最大正方形的边长（正方形的范围不能超出矩阵的行数和列数），在该边长范围内寻找只包含 1 的最大正方形；
3、每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1。

Python版本

#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix ):
        # write code here
        # 特殊情况处理
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        # 初始化
        maxSide = 0
        rows, columns = len(matrix), len(matrix[0])
        # 双层遍历
        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == '1':
                    # 遇到一个 1 作为正方形的左上角
                    maxSide = max(maxSide, 1)
                    # 计算可能的最大正方形边长
                    currentMaxSide = min(rows - i, columns - j)
                    for k in range(1, currentMaxSide):
                        # 判断新增的一行一列是否均为 1
                        flag = True
                        if matrix[i + k][j + k] == '0':
                            break
                        for m in range(k):
                            if matrix[i + k][j + m] == '0' or matrix[i + m][j + k] == '0':
                                flag = False
                                break
                        if flag:
                            maxSide = max(maxSide, k + 1)
                        else:
                            break
        # 返回最后结果
        maxSquare = maxSide * maxSide
        return maxSquare

复杂度分析

时间复杂度：其中 m 和n 是矩阵的行数和列数。需要遍历整个矩阵寻找每个 1，遍历矩阵的时间复杂度是 O(mn)。对于每个可能的正方形，其边长不超过 m 和 n 中的最小值，需要遍历该正方形中的每个元素判断是不是只包含 1，遍历正方形时间复杂度是 。总时间复杂度是 。

空间复杂度O(1)：额外使用的空间复杂度为常数

算法思想二：动态规划

解题思路

方法一虽然直观，但是时间复杂度太高
方法二使用动态规划降低时间复杂度。我们用dp(i,j) 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。如果能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。
对于每个位置 (i, j)，检查在矩阵中该位置的值：
1、如果该位置的值是 0，则 dp(i,j)=0，因为当前位置不可能在由 1 组成的正方形中；
2、如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

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

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

图解：

JAVA版本

import java.util.*;


public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        // write code here
        int maxSide = 0;
        // 特殊情况
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        // dp 数组
        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 数组初始数据
                        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;
    }
}