LeetCode-221. 最大正方形

一时失言乱红尘 2024-03-23 10:06 93阅读 0赞

#### 目录 ####

*   *  题目思路
     *  动态规划
     *  动态规划(优化)

题目来源  
[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

如果无法理解的话，可以简单画一个图自己理解一下  
![在这里插入图片描述][6856f58ae5ea4544a26130fe2e23e755.png]

### 动态规划 ###

*  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”\]\]为例  
![在这里插入图片描述][2bb9a2f44792450e97ce9b3d97d38417.png]

代码实现

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

![在这里插入图片描述][9b6f62ae51224080abbefe4073041b4f.png]

### 动态规划(优化) ###

我们其实可以不用进行初始化，但我们需要把数组扩大一格，这样就不用考虑Math.min(dp\[i-1\]\[j\],Math.min(dp\[i-1\]\[j-1\],dp\[i\]\[j-1\]))+1左边，上边，左上角了  
![在这里插入图片描述][7ed2f02312924ea6876107051fe724f1.png]

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

![在这里插入图片描述][60a87a5f13874dda8e8fd5bef316efa7.png]

[221.]: https://leetcode.cn/problems/maximal-square/
[6856f58ae5ea4544a26130fe2e23e755.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2185a3e026c445d69b487fc5640ffe29.png
[2bb9a2f44792450e97ce9b3d97d38417.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e0ad5ddbbafd43c2bc43305ce9d743b2.png
[9b6f62ae51224080abbefe4073041b4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/cd1fda6d2c124014ac588426f3be0b7c.png
[7ed2f02312924ea6876107051fe724f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d88f069d4351461e8637e2f821a1cc5f.png
[60a87a5f13874dda8e8fd5bef316efa7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/f07e043829f54d1a9bcb9ed1234a137d.png