跳到主要内容

正方形题库

最大正方形​

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

示例1:

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例2:

输入：matrix = [["0","1"],["1","0"]]
输出：1

方案 动态规划​

思路：

  1. 状态定义: dp[i][j]表示以(i,j)为右下角，且只包含1的正方形的边长最大值
  2. 状态转移方程:
  • 如果该位置的值是0，则方程为dp[i][j]=0
  • 如果i=0||j=0，则方程为dp[i][j]=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. 初始化状态: dp 初始为 0
  2. 问题答案: dp 元素中的最大值

:::details 点击查看代码

function maximalSquare(matrix) {
    let maxSide=0;
    const row=matrix.length;
    const col=matrix[0].length;
    if(!matrix||row==0||col==0){
        return maxSide;
    }
    const dp=new Array(row).fill(0).map(()=>new Array(col).fill(0));
    for(let i=0;i<row;i++){
        for(let j=0;j<col;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],dp[i-1][j-1],dp[i][j-1]])+1;
                }
            }
            maxSide=Math.max(maxSide,dp[i][j]);
        }
    }
    let maxSquare=maxSide*maxSide;
    return maxSquare;
};

:::

性能分析:

  • 时间复杂度: O(mn)
  • 空间复杂度: O(mn)