【面试刷题-力扣经典】动规：221. 最大正方形

红太狼 2021-09-21 06:04 303阅读 0赞

**【题目】**

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

输入:

1 0 1 0 0  
1 0 1 1 1  
1 1 1 1 1  
1 0 0 1 0

输出: 4

**【思路】**

dp\[x\]\[y\] 代表的是正方形的最右下角是x,y的时候，正方形的边长

从 (0,0)(0,0) 开始，对原始矩阵中的每一个 1，我们将当前元素的值更新为  
![在这里插入图片描述][20200413204759203.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

(1,3) 处的 2 表示到该索引为止有个边长为 2 的正方形。同样的，(1,2)(1,2) 和 (2,2)(2,2) 处的 2 也表示到该索引为止有边长为 2 的正方形。到了 (3,3)(3,3)，原始矩阵中 (3,3)(3,3) 中的 1，形成了边长为 3 的正方形，所以在 (3,3)(3,3) 中应该为 3。

现在考虑索引 (3,4)(3,4) 的情况，到 (3,4)(3,4) 所能形成的最大正方形为 2，所以 (3,4)(3,4) 应为 2。

**【代码】**

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

[20200413204759203.png]: https://img-blog.csdnimg.cn/20200413204759203.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/1f308cc106094020b8cd9b670f80b499.png