221. *大正方形(JS实现)

221. *大正方形(JS实现)
1 题目
在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的*大正方形,并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
链接:https://leetcode-cn.com/problems/maximal-square
2 思路
这道题可以用动态规范的方法来做,d[i][j]为右下角为matrix[i][j]的符合题意的正方形*大边长,那么状态转移方程,d[i+1][j+1] = Math.min(d[i][j+1], d[i][j], d[i+1][j]) + 1,可以自己画图看一下是不是这个规律
3代码
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    let rows = matrix.length;
    if (rows === 0) return 0;
    let cols = matrix[0].length;
    const d = [];
    let maxEdge = 0;
    for (let i=0; i<rows; i++) {
        if (!d[i]) d[i] = [];
        for (let j=0; j<cols; j++) {
            if (i > 0 && j > 0 && matrix[i][j] === ‘1’ && d[i-1][j-1] > 0) {
                let m = i;
                for (; m>=i-d[i-1][j-1]; m–) {    //遍历当前行看是否满足正方形条件
                    if (matrix[m][j] === ‘0’) {
                        break;
                    }
                }
                let n = j;
                for (; n>=j-d[i-1][j-1]; n–) {   //遍历当前列看是否满足正方形条件
                    if (matrix[i][n] === ‘0’) {
                        break;
                    }
                }
                let currentEdge = Math.min(i-m, j-n);
                d[i][j] = currentEdge;
                maxEdge = Math.max(d[i][j], maxEdge)
            } else {
                d[i][j] = parseInt(matrix[i][j]);
                if (maxEdge === 0) maxEdge = Math.max(d[i][j], maxEdge);
            }
        }
    }
    return maxEdge * maxEdge;
};