221. 最大正方形

[webVueBlog]

221. 最大正方形

Description

Difficulty: 中等

Related Topics: 数组, 动态规划, 矩阵

在一个由 '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

示例 3：

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

提示：

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

Solution

Language: JavaScript

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    if(!matrix||matrix.length===0||matrix[0].length===0){
      return 0
    } 
    // 1.设一个变量存放最长边
    let maxSide = 0;
    // 长宽
    let row = matrix.length;
    let column = matrix[0].length
    // 2.声明一个数组来存放每个点的最长边
    let dp=[]
    for(let i=0;i<row;i++){
        dp.push(new Array(column))
    }
    //3.遍历所有节点
    for(let i=0;i<matrix.length;i++){
        for(let j=0;j<matrix[i].length;j++){
            // 如果当前的节点等于1；
            if(matrix[i][j]=='1'){
                //且该节点的下标是0 0
                if(i==0||j==0){
                    dp[i][j]=1
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1
                }
            }else{
                dp[i][j]=0;
            }
          
            maxSide = Math.max(dp[i][j],maxSide)
        }
    }
    return Math.pow(maxSide,2)
};