leetcode中等难度题 -- 33.最大正方形

问题描述

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

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

解题思路：动态规划

1. 定义二维数组dp[i][j]，表示以(i, j)为右下角，只包含1的正方形边长的最大值

2. 初始情况：

3.状态转移方程

代码实现（js） 

var maximalSquare = function(matrix) {
    let max_len = 0
    // 1.定义数组
    let dp = new Array(matrix.length)
    for(let i = 0; i < matrix.length; i++){
        dp[i] = new Array(matrix[0].length).fill(0)
    }
    // 2.状态转移方程
    for(let i = 0; i < dp.length; i++){
        for(let j = 0; j < dp[0].length; j++){
            if(matrix[i][j] === '1'){
                // 如果当前元素为1
                if(i === 0 || j === 0){
                    dp[i][j] = 1
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                }   
            }
            max_len = Math.max(max_len, dp[i][j])
        }
    }
    return max_len * max_len
};