Leetcode 自带解答写的很好.
相关题目:
枚举左上角,对每一个左上角,
Time = O(n^2), space = O(n^2)
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int[][] maximalSquare = new int[matrix.length + 1][matrix[0].length + 1];
for (int i = 0; i < maximalSquare.length; i++) {
maximalSquare[i][0] = 0;
}
for (int j = 0; j < maximalSquare[0].length; j++) {
maximalSquare[0][j] = 0;
}
int maximalLength = 0;
for (int i = 1; i < maximalSquare.length; i++) {
for (int j = 1; j < maximalSquare[0].length; j++) {
if (matrix[i - 1][j - 1] == '1') {
maximalSquare[i][j] = Math.min(Math.min(maximalSquare[i - 1][j],
maximalSquare[i][j - 1]),
maximalSquare[i - 1][j - 1]) + 1;
maximalLength = Math.max(maximalLength, maximalSquare[i][j]);
} else {
maximalSquare[i][j] = 0;
}
}
}
return maximalLength * maximalLength;
}
}