221.最大正方形 中等

问题：

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

回答：

初始化一个二维数组，值默认填充为0，长和宽均比当前矩阵加一，令dp[i + 1][j + 1]对应matrix[i][j] 以覆盖边界

遍历二维数组，当元素值为1时，填充dp数组，正方形需要满足，上，左，坐上均为1，所以木桶效应找最短的那条边 + 1；

找到最长的边，相乘得到最后结果

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    //宽高多设置一圈
    let dp = new Array(m + 1).fill().map(() => {
        return new Array(n + 1).fill(0)
    })
    let max = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                //此时的dp[i + 1][j + 1]实际为matrix[i][j]所在元素
                dp[i + 1][j + 1] = Math.min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1;
                max = Math.max(max, dp[i + 1][j + 1])
            }
        }
    }
    return max * max;
};