Maximal Square
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.
Example
For example, given the following matrix:
<code>1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 </code>
Return 4.
Solution: DP side[i][j] 表示以(i,j)这个点为右下角可以组成的最大square的边长
由下图可知，大正方形由三个小正方形和(i,j)这个点这个点决定
side[i][j] = min(side[i-1][j-1], side[i][j-1], side[i-1][j]) +1 //when matrix[i][j]==1
= 0 //when matrix[i][j] = 0
public int maxSquare(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
//side[i][j] = the length of the max square which (i,j) is the at right bottom corner.
int[][] side = new int[matrix.length][matrix[0].length];
int max = 0;
for (int i = 0; i < matrix.length; i++) {
side[i][0] = matrix[i][0];
max = Math.max(max, side[i][0]);
}
for (int j = 0; j < matrix[0].length; j++) {
side[0][j] = matrix[0][j];
max = Math.max(max, side[0][j]);
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) {
side[i][j] = 0;
} else {
side[i][j] = Math.min(side[i - 1][j], Math.min(side[i][j - 1], side[i - 1][j - 1])) + 1;
max = Math.max(max, side[i][j]);
}
}
}
return max * max;
}
