【题目】
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input: 1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0 Output: 4
【思路】
- dp square面积和三个有关
- 注意特殊空集条件
【代码】
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix.length==0)
return 0;
int dp[][]=new int[matrix.length+1][matrix[0].length+1];
int ans=0;
for(int i=1;i<matrix.length+1;i++){
for(int j=1;j<matrix[0].length+1;j++){
if(matrix[i-1][j-1]=='1'){
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
ans=Math.max(ans,dp[i][j]);
}
}
}
return ans*ans;
}
}