Q:给定一个包含0和1的二维二进制矩阵,找出只包含1的最大正方形并返回其面积。
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
A:引用:https://blog.csdn.net/fly_fly_zhang/article/details/90637370
我们初始化一个二维矩阵dp, dp [ i ] [ j ] 表示以它为右下角的最大正方形边长。遍历原矩阵,每找到一个1,就求以它为右下角的最大正方形边长。
正方形的判断是一个从小到大的过程:
先看一个节点是否为1;
再看2/2范围是否满足条件。
依次,直到n/n范围是否满足条件。
由此,这是后一个结果是否成立基于前一个结果的成立 ,因此使用dp处理。
dp[i][j] 角标的左边还有上边也就是以其为原点的第二象限,实际上已经是已知的。因此我们将其设置为正方形的右下角,恰是应用了已经条件。
而其它三个顶点的位置,实际上可以根据和它相邻的已推算处的正方形边长得到。其存在以下公式:
\[DP[i][j] = min(DP[i-1][j-1], DP[i-1][j], DP[i, j-1]) + 1\]
DP[i-1][j-1] 确定左上角位置
DP[i-1][j] 确定左下角位置
DP[i, j-1] 确定右上角位置。
根据这三个正方形边长的最小值就可以确定对应位置。
public int maximalSquare(char[][] matrix) {
if(matrix==null||matrix.length==0||matrix[0]==null||matrix[0].length==0)
return 0;
int row=matrix.length;
int col=matrix[0].length;
int max=0;
//因为矩阵最上面的点是以它自己为一个矩阵的,但是为了计算方便
//我们假设它有
int [][] dp=new int[row+1][col+1];
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++){
if(matrix[i-1][j-1]=='1'){
//得到最短的正方形边长
dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
max=Math.max(dp[i][j],max);
}
}
}
return max*max;
}