Leetcode221——最大正方形

题目连接

题意很好理解，这里我根据官方的题解，总结出两种方法

1. 暴力法（搜索或者全部遍历）
2. DP动态规划

1.暴力~

由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。

• 遍历矩阵的每个元素，每次遇到1，把此当作正方形的左上角，然后看此点的右下角是否为1，如果不是，则退出看下一个点，如果是则看右下角的左边的点和右下角右边的点
• 每次能满足正方形的条件，则向右下延展，每次再下方新增一行以及在右方新增一列，判断新的点是否为1

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();//l列、行
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < columns; j++)
            {
                if (matrix[i][j] == '1')
                {
                    // 遇到一个 1 作为正方形的左上角
                    maxSide = max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = min(rows - i, columns - j);
                    for (int k = 1; k < currentMaxSide; k++)
                    {
                        // 判断新增的一行一列是否均为 1
                        bool 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)
                        {
                            maxSide = max(maxSide, k + 1);
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
};

此方法时间复杂度较高

2.DP

动态规划可以有效降低时间复杂度，用dp[][]数组表示以相应位置点作为右下角可以构成符合条件正方形的边长，如果能计算出所有dp[][]的值，那么dp数组中的最大值就是符合题目条件的最大正方形边长，其平方就是最大正方形的面积

具体步骤，对于每个位置dp[i][j]

• 如果该位置的值是 0，则dp[i][j]=0因为以此位置作为正方形右下角显然不符合题目条件
• 如果该位置值是1，则dp[i][j]的值由其上方、左方和左上方的三个相邻位置的dp值确定，具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 11，状态转移方程如下：
  dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

此外还需要考虑边界，如果此点为1且在第一行或者第一列，显然不能作为正方形右下角，则此点dp值只能为1

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;
    }
}