MaxSquare.js

"use strict";
exports.__esModule = true;
/**
 * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
 * @param {string[][]} matrix
 * @return {number}
 */
function maxSquare(matrix) {
    // 参数验证
    if (!Array.isArray(matrix) || !Array.isArray(matrix[0])) {
        throw new TypeError(matrix + " is not a valid matrix");
    }
    // 获取二维数组的宽高
    var rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
    // 设置一个动态二维数组 每一位表示以该位左上角那位能构成的正方形的最大边长
    var dp = new Array(rows + 1);
    for (var i = 0; i < dp.length; i++) {
        dp[i] = new Array(cols + 1).fill(0);
    }
    // 设置一个最大边长变量
    var maxLens = 0;
    for (var i = 1; i <= rows; i++) {
        for (var j = 1; j <= cols; j++) {
            if (matrix[i - 1][j - 1] === '1') {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1;
                maxLens = Math.max(dp[i][j], maxLens);
            }
        }
    }
    // 返回最大正方形的面积
    return maxLens * maxLens;
}
exports.maxSquare = maxSquare;