Leetcode 221 最大正方形(DP)

墨蓝 2022-08-29 14:54 146阅读 0赞

#### 题目重述 ####

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]

输入：matrix = \[\[“1”,“0”,“1”,“0”,“0”\],\[“1”,“0”,“1”,“1”,“1”\],\[“1”,“1”,“1”,“1”,“1”\],\[“1”,“0”,“0”,“1”,“0”\]\]  
输出：4  
示例 2：  
![在这里插入图片描述][20210717003239637.png]

输入：matrix = \[\[“0”,“1”\],\[“1”,“0”\]\]  
输出：1  
示例 3：

输入：matrix = \[\[“0”\]\]  
输出：0

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximal-square  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

`dp[i][j]`代表以(i，j)位置为右下角的有效正方形的边长

状态转移方程

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

我们考虑这样一件事情：当前格、上、左、左上都不能受 0 的限制，才能成为正方形，所以去找另外三个点的最小值，但凡有一个是0，那么都不可能构成正方形，反之，如果都是1，那么找最小的边长就行

迭代即可

#### Java实现 ####

class Solution {
        
        public int maximalSquare(char[][] matrix) {
        
            if(matrix.length == 0)
            {
        
                return 0;
            }
            int maxLineLength = 0;
            // dp[i][j]代表以i，j位置为右下角的有效正方形的边长
            int[][] dp = new int[matrix.length][matrix[0].length];
    
            for (int i = 0; i < matrix.length; i++) {
        
                for (int j = 0; j < matrix[i].length; j++) {
        
    
                    // 如果是1，则有可能构成有效正方形
                    if(matrix[i][j]=='1')
                    {
        
                        // base case
                        if(i==0 || j==0)
                        {
        
                            dp[i][j] = 1;
                        }else
                        {
        
                            // dp迭代
                            dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                        }
                        maxLineLength = Math.max(dp[i][j],maxLineLength);
                    }
                }
            }
            return maxLineLength*maxLineLength;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20220829/9985472d301b4d198594d87a9491443b.png
[20210717003239637.png]: /images/20220829/76352b20bcc047fb8a72e69258212520.png