当前位置：网站首页>【动态规划】221. 最大正方形

【动态规划】221. 最大正方形

2022-04-23 13:07:00 【不爱研究的研究僧】

题目：

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

 

 

题解：

 

dp 具体定义：dp[i + 1][j + 1] 表示 「以第 i 行、第 j 列为右下角的正方形的最大边长」
为何不是 dp[i][j]

任何一个正方形，我们都「依赖」当前格 左、上、左上三个方格的情况，但第一行的上层已经没有格子，第一列左边已经没有格子，需要做特殊 if 判断来处理，为了代码简洁，我们 假设补充 了多一行全 '0'、多一列全 '0'

 

此时 dp 数组的大小也明确为 new dp[height + 1][width + 1]
初始值就是将第一列 dp[row][0] 、第一行 dp[0][col] 都赋为 0，相当于已经计算了所有的第一行、第一列的 dp 值
题目要求面积。根据 「面积 = 边长 x 边长」可知，我们只需求出 最大边长 即可
定义 maxSide 表示最长边长，每次得出一个 dp，就 maxSide = max(maxSide, dp);
最终返回 return maxSide * maxSide;

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length < 1 || matrix[0].length < 0) {
            return 0;
        }
        int h = matrix.length;
        int w = matrix[0].length;
        int maxLen = 0;
        int[][] dp = new int[h + 1][w + 1]; // 相当于已经预处理新增第一行、第一列均为0
        for (int i = 0 ; i < h; i++) { //遍历matrix
            for (int j = 0; j < w; j++) {
                if (matrix[i][j] == '1') {
                    //取左边、右边、左上最小长度加上当前单元格长度1
                    //注意左边、右边、左上是以[i + 1][j + 1]为基准，而不是[i][j]
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i + 1][j], dp[i][j + 1]), dp[i][j]) + 1; 
                }
                maxLen = Math.max(maxLen, dp[i + 1][j + 1]);
            }
        } 
        return maxLen * maxLen;
    }
}

参考：力扣

版权声明
本文为[不爱研究的研究僧]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43955488/article/details/124361049

边栏推荐

猜你喜欢

随机推荐