目录

一、题目描述

二、思路讲解

三、Java代码实现 

四、时空复杂度分析

一、题目描述

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

二、思路讲解

        将每个位置（i，j）作为正方形的右下角，使用dp[i][j]表示这个正方形只有1的最大面积。那么，

        dp[i][j] = min{ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] } + 1 

        然后找到dp数组中的最大值即可。

三、Java代码实现 

class Solution {public int maximalSquare(char[][] matrix) {int m = matrix.length;int n = matrix[0].length;int [][]dp = new int[m][n];//将上边和左边的边界初始化for(int i=0; i<m; i++){if(matrix[i][0]=='1'){dp[i][0]=1;}}for(int i=0; i<n; i++){if(matrix[0][i]=='1'){dp[0][i]=1;}}//动态规划计算每个位置的值for(int i=1; i<m; i++){for(int j=1; j<n; j++){if(matrix[i][j]=='1'){dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;}}}//找到dp中的最大值int big = 0;for(int i=0; i<m; i++){for(int j=0; j<n; j++){big = Math.max(big, dp[i][j]);}}return big*big;}
}

四、时空复杂度分析

        时间复杂度：        O(MN)

        空间复杂度：        O(MN)