当前位置：首页 > article >正文

Leetcode 221-最大正方形

article 2025/2/21 23:33:55

题目

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

在这里插入图片描述

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’

题解 (动态规划法)

题解参考Leetcode官方
可以使用动态规划降低时间复杂度。用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。

对于每个位置 (i,j)，检查在矩阵中该位置的值：

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

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

即若形成正方形（非单 1），以当前为右下角的视角看，则需要：当前格、上、左、左上都是 1
可以换个角度：当前格、上、左、左上都不能受 0 的限制，才能成为正方形：
图片转载自lzhlyle
在这里插入图片描述
上面详解了三者取最小的含义：

图 1：受限于左上的 0
图 2：受限于上边的 0
图 3：受限于左边的 0
数字表示：以此为正方形右下角的最大边长
黄色表示：格子 ? 作为右下角的正方形区域
就像木桶的短板理论那样——附近的最小边长，才与 ? 的最长边长有关。
此时已可理解递推公式

算法步骤

动态规划：
1.dp[i][j]:表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。
需要matrix[i][j]==‘1’

2.动态转移方程：
当matrix[i][j]==‘1’
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1

3.初始化：
当matrix[i][j]==‘1’ && i=0 || j=0
dp[0][j]=1,dp[i][0]=1

4.遍历：
i从1开始到m，j从1开始到n

5.返回值：
通过比较Math.max(res,dp[i][j])不断更新最大正方形边长res的值
return res*res


class Solution {
    public int maximalSquare(char[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int res=0;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    //初始化边界值
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    }else
                    {
                        dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    }
                    res=Math.max(res,dp[i][j]);
                }
            }
        }
        return res*res;
    }
}