目录
一、题目描述
在一个由 ‘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)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125003.html
