221. Maximal Square

[Tcdian]

221. Maximal Square

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

Example

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

[Tcdian]

Solution ( DP )

• JavaScript Solution

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    const dp = Array.from(new Array(matrix.length), () => new Array(matrix[0].length).fill(0));
    let maxSideLen = 0;

    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (i === 0 || j === 0) {
                dp[i][j] = Number(matrix[i][j]);
            } else if (matrix[i][j] === '1') {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
            }
            maxSideLen = Math.max(maxSideLen, dp[i][j]);
        }
    }
    
    return maxSideLen * maxSideLen;
};