221. 最大正方形

爱被打了一巴掌 2023-03-04 14:28 6阅读 0赞

# 题目： #

[221. 最大正方形][221.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解：动态规划 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

# 代码：动态规划 #

public class code221 { 
    
        public static int maximalSquare(char[][] matrix) { 
            // base condition
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            { 
                return 0;
            }
            // m 行 n 列
            int m = matrix.length;
            int n = matrix[0].length;
            int maxSide = 0;
    
            // dp(i, j) 是以 matrix(i - 1, j - 1) 为 右下角 的正方形的最大边长
            // dp(i + 1, j + 1) 是以 matrix(i, j) 为 右下角 的正方形的最大边长
            // dp[i + 1][j + 1] 表示 「以第 i 行、第 j 列为右下角的正方形的最大边长」
            // 相当于已经预处理新增第一行、第一列均为0
            int dp[][] = new int[m + 1][n + 1];
    
            for(int i = 0; i < m; i++)
            { 
                for(int j = 0; j < n; j++)
                { 
                    if(matrix[i][j] == '1')
                    { 
                        dp[i + 1][j + 1] = Math.min(Math.min(dp[i + 1][j], dp[i][j + 1]),dp[i][j]) + 1;
                        maxSide = Math.max(maxSide, dp[i + 1][j + 1]);
                    }
                }
            }
            return maxSide * maxSide;
        }
    
        public static void main(String[] args) { 
            char[][] matrix = {  { '1','0','1','0','0'},
                                { '1','0','1','1','1'},
                                { '1','1','1','1','1'},
                                { '1','0','0','1','0'} };
            int res = maximalSquare(matrix);
            System.out.println(res);
        }
    }

# 参考： #

1.  [理解 三者取最小+1][_1]
2.  [最大正方形][Link 1]
3.  [统计全为 1 的正方形子矩阵][1]

[221.]: https://leetcode-cn.com/problems/maximal-square/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230208/563fbdf0481745df9e5bb0b7db732ab0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20230208/6239d84d71cd4cb19279bc57a659fa49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: /images/20230208/572ae58a12cb41b1a6e9d33cccc2a2cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: /images/20230208/5ebb1c3b795647038959eb27d4f2c9df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: /images/20230208/8fdab5bf4ecc4a668078bdea4d484b55.png
[_1]: https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/
[Link 1]: https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
[1]: https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/solution/tong-ji-quan-wei-1-de-zheng-fang-xing-zi-ju-zhen-2/