221. 最大正方形

川长思鸟来 2023-10-11 18:04 24阅读 0赞

打卡!!!每日一题

今天继续给大家分享一道动态规划类型的题目，不过该题目的状态转移方程比较难以理解，我会详细的给大家分析一下

题目描述：

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

题目示例：  
![在这里插入图片描述][dba8274dcc1040918ab395bbedeb7276.png_pic_center]

![在这里插入图片描述][dfaa01e75d1c4bd890f871ae85e4e93c.png_pic_center]

本题思路很简单，直接暴力解决，两个for循环遍历，一直遍历到最右下的结点，然后找到一个面积最大值，由于时间复杂度太高，也对不起我们的智商（PS：听我吹吹牛就算了，在真正笔试或者面试的时候一定要用最快的速度解决出来，只要能AC就是厉害），下面我们讨论一下动态规划的解决办法。

我们定义dp\[i\]\[j\]，表示以（i,j）为右下角的，且只包含 1 的正方形的边长最大值  
![在这里插入图片描述][fb0d1dd514bc4765a9733b8d3ea072bf.png_pic_center]

通俗来讲，就像上图所示红色区域下对应的正方形，当然这个正方形可能没那么大，我只是随便画了一个供大家理解一下右下角的含义。

如果我们能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。

那么如何计算 dp 中的每个元素值呢？对于每个位置 (i, j)，检查在矩阵中该位置的值：

*  如果该位置的值是 0，则 dp(i, j) = 0，因为当前位置不可能在由 1 组成的正方形中；
 *  如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

![在这里插入图片描述][27643c4a4cfb4599bb9b3f38bf2080f0.png_pic_center]

我帮大家理解一下为啥取这三个里面的最小值  
![在这里插入图片描述][e5166d86939a4ce4965438c319d98d15.png_pic_center]

我们假设A,B,C的形状如下：  
![在这里插入图片描述][273a4db76e234dba8987ab9dc2d5a65c.png_pic_center]

说明E区域里面的值一定是0，否则的话C的边长就可以取2了

如果D的边长取A的边长+1，即D的边长=4，那么其组成的大正方形，一定包含E区域，这就不合理了，因为题目要求的是我们的正方形必须全部为1

如果还是不理解，下面留言吧，实在不行，我有空录制个视频来给大家讲解一下。

如果这个理解了，代码就很简单了：

public int maximalSquare(char[][] matrix) {
        
            int row = matrix.length;
            int coloumn = matrix[0].length;
            if (row <= 1 && coloumn <= 1) {
        
                return matrix[0][0];
            }
            int[][] dp = new int[row][coloumn];
            for (int r = 0; r < row; r++) {
        
                for (int c = 0; c < coloumn; c++) {
        
                    if (matrix[r][c] == '0') {
        
                        dp[r][c] = 0;
                    } else {
        
                        if (r - 1 < 0 || c - 1 < 0) {
        
                            dp[r][c] = 1;
                        } else {
        
                            dp[r][c] = Math.min(Math.min(dp[r][c - 1], dp[r - 1][c]), dp[r - 1][c - 1]) + 1;
                        }
                    }
                }
            }
            int max = dp[0][0];
            for (int i = 0; i < row; i++) {
        
                for (int j = 0; j < coloumn; j++) {
        
                    max = Math.max(dp[i][j], max);
                }
            }
            return max * max;
        }

[dba8274dcc1040918ab395bbedeb7276.png_pic_center]: https://img-blog.csdnimg.cn/dba8274dcc1040918ab395bbedeb7276.png#pic_center
[dfaa01e75d1c4bd890f871ae85e4e93c.png_pic_center]: https://img-blog.csdnimg.cn/dfaa01e75d1c4bd890f871ae85e4e93c.png#pic_center
[fb0d1dd514bc4765a9733b8d3ea072bf.png_pic_center]: https://img-blog.csdnimg.cn/fb0d1dd514bc4765a9733b8d3ea072bf.png#pic_center
[27643c4a4cfb4599bb9b3f38bf2080f0.png_pic_center]: https://img-blog.csdnimg.cn/27643c4a4cfb4599bb9b3f38bf2080f0.png#pic_center
[e5166d86939a4ce4965438c319d98d15.png_pic_center]: https://img-blog.csdnimg.cn/e5166d86939a4ce4965438c319d98d15.png#pic_center
[273a4db76e234dba8987ab9dc2d5a65c.png_pic_center]: https://img-blog.csdnimg.cn/273a4db76e234dba8987ab9dc2d5a65c.png#pic_center