刷题91—动态规划（八）

137.最大正方形

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

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

示例:

输入:

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

输出: 4

题目分析

1. 判断二维矩阵的长度，如果长度等于0，return 0；
2. 定义二维数组dp,并赋初值0；
3. 遍历二维矩阵，dp[i][j]==1：正方形最右下角的一个点，因此当前点的上、左、上左三个方向的点都为1，是其他正方形的最右下角的点，即dp[i-1][j],dp[i-1][j-1],dp[i][j-1]；
4. 判断i，j的值是否为0，为0 时，此点在矩形最左上角，没有上、左、上左三个方向，因此dp[i][j] = parseInt(matrix[i][j])，max = Math.max(max, dp[i][j])；
5. 当 二维矩阵的点为1时，即matrix[i][j] == '1' ， dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1，max = Math.max(max, dp[i][j])；
6. 其他情况，dp[i][j]=0；
7. 返回最大边长的平方，即return max * max；

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    let m = matrix.length;
    if(m == 0) return 0;
    let n = matrix[0].length;
    
    let dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0));
    let max = 0;    
    for(let i=0; i<m; i++){
        for(let j=0; j<n; j++){
            if(i ==0 || j==0){
                dp[i][j] = parseInt(matrix[i][j]);
                max = Math.max(max, dp[i][j]);
                continue;
            }else if(matrix[i][j] == '1'){
                dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1;
                max = Math.max(max, dp[i][j]);
            }else{
                dp[i][j] = 0;
            }
        }
    }
    return max * max;
};