LeetCode-221. 最大正方形-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode-221. 最大正方形。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源
221. 最大正方形

题目思路

现在我们需要找到只包含 ‘1’ 的最大正方形。首先，我们可以初始化一个和原始矩阵相同大小的矩阵 dp，用来记录每个格子所在的最大正方形的边长。
对于第一行和第一列的格子，它们的 dp 值只能是 0 或 1，因为它们的左侧或上侧没有格子。我们可以直接将原始矩阵的值转换为 dp 矩阵的值。
对于其他格子，如果它的值为 ‘1’，则它所在的最大正方形的边长至少为 1。我们可以根据它左侧、上侧和左上方格子的 dp 的最小值+1来计算当前格子的 dp 值

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

如果无法理解的话，可以简单画一个图自己理解一下
LeetCode-221. 最大正方形

动态规划

1.确定dp数组以及下标的含义

用 dp(i, j) 表示以 matrix[i][j] 为右下角的最大正方形的边长。

2.确定递推公式

如果它的值为 ‘1’，则它所在的最大正方形的边长至少为 1。我们可以根据它左侧、上侧和左上方格子的 dp 的最小值+1来计算当前格子的 dp 值

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

3.dp数组如何初始化

对于第一行和第一列的格子，它们的 dp 值只能是 0 或 1，因为它们的左侧或上侧没有格子。我们可以直接将原始矩阵的值转换为 dp 矩阵的值。

        for(int i = 0;i<row;i++){
            dp[i][0] = matrix[i][0]-'0';
            res = Math.max(res,dp[i][0]);
        }
        for(int j = 1;j<col;j++){
            dp[0][j] = matrix[0][j]-'0';
            res = Math.max(res,dp[0][j]);
        }

4.确定遍历顺序

从递推公式dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1可知，遍历顺序从上到下，从左到右

5.举例推导dp数组

以输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]为例
LeetCode-221. 最大正方形

代码实现

class Solution {
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int res = 0;
        int[][] dp = new int[row][col];
        for(int i = 0;i<row;i++){
            dp[i][0] = matrix[i][0]-'0';
            res = Math.max(res,dp[i][0]);
        }
        for(int j = 1;j<col;j++){
            dp[0][j] = matrix[0][j]-'0';
            res = Math.max(res,dp[0][j]);
        }
        for(int i = 1;i<row;i++){
            for(int j = 1;j<col;j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                    res = Math.max(res,dp[i][j]);
                }
                
            }
        }
        return res*res;
    }
}

LeetCode-221. 最大正方形

动态规划(优化)

我们其实可以不用进行初始化，但我们需要把数组扩大一格，这样就不用考虑Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1左边，上边，左上角了
LeetCode-221. 最大正方形

class Solution {
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int res = 0;
        int[][] dp = new int[row+1][col+1];
        for(int i = 1;i<=row;i++){
            for(int j = 1;j<=col;j++){
                if(matrix[i-1][j-1] == '1'){
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                    res = Math.max(res,dp[i][j]);
                }
                
            }
        }
        return res*res;
    }
}