欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode221——最大正方形

程序员文章站 2022-07-13 21:59:13
...

题目连接

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

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

1.暴力~

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

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

Leetcode221——最大正方形

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

Leetcode221——最大正方形

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