221. [✔][M]最大正方形

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

---

题解：

动态规划解题套路框架

// @lc code=start
function maximalSquare(matrix: string[][]): number {
    let m = matrix.length;
    let n = matrix[0].length;

    let side = 0;

    let dp = new Array(m).fill(1).map(() => new Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        dp[i][0] = parseInt(matrix[i][0]);
    }

    for (let j = 0; j < n; j++) {
        dp[0][j] = parseInt(matrix[0][j]);
    }

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === '1') {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1;
            } else {
                continue;
            }
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            side = Math.max(side, dp[i][j]);
        }
    }

    return side * side;
};
// @lc code=end