LeetCode百题【最大正方形】

题目描述

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

示例 1：

1 2	`输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4`

示例 2：

1 2	`输入：matrix = [["0","1"],["1","0"]] 输出：1`

示例 3：

1 2	`输入：matrix = [["0"]] 输出：0`

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

解法

动态规划
- 我们定义 dp[i][j]表示以 (i, j)为右下角，且只包含 1 的正方形的边长最大值。
- dp[i][j]的值由其左，右左上角决定，当三者都为1时才可拓展正方形
- 状态转移方程为：Min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
- 维护dp的最大值，即为最大正方形的边

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSize=0;
        //1.特殊判断
        if (matrix.length==0||matrix[0].length==0){
            return maxSize;
        }
        int row=matrix.length;
        int col=matrix[0].length;
        //2.定义dp
        int[][] dp=new int[row][col];
        //3.遍历
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j]=='1'){
                    //当在第一行或第一列
                    if (i==0||j==0){
                        dp[i][j]=1;
                    }else {
                        //动态转移
                        dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    }
                    //维护最大边
                    maxSize=Math.max(dp[i][j],maxSize);
                }
            }
        }
        return maxSize*maxSize;
    }
}