题目
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0Return 4.
解法很巧妙，我也是看了discuss，首先列出最左一列和最上面一列，剩下的解法可以看这个
Basic idea is to iterate over all columns and rows of a matrix (starting with i=j=1). If value in a cell>0 and cells to the north, west, and north-west are >0, pick smallest value of those 3 cells, take it's square root, add 1, and assign square of new value to current cell. For example given matrix
1 1 1 1 1 1
1 1 1 0 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 0 1
We get:
1 1 1 1 1 1
1 4 4 0 1 4
1 4 9 1 1 4
1 4 9 4 4 4
1 4 9 9 9 9
1 4 9 16 0 1
Our answer is the largest value in new matrix: 16
代码
public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length == 0) {
return 0;
}
int res = 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] sq = new int[m][n];
for(int i = 0; i < m; i++) {
if(matrix[i][0] == '1') {
sq[i][0] = 1;
res = 1;
} else {
sq[i][0] = 0;
}
}
for(int j = 0; j < n; j++) {
if(matrix[0][j] == '1') {
sq[0][j] = 1;
res = 1;
} else {
sq[0][j] = 0;
}
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(matrix[i][j] == '1') {
int min = Math.min(Math.min(sq[i][j-1], sq[i-1][j]), sq[i-1][j-1]);
//if(min != 0) {
sq[i][j] = (int)Math.pow(Math.sqrt(min)+1, 2);
res = Math.max(res, sq[i][j]);
//}
}
}
}
return res;
}
}
/********************************
* 本文来自博客 “李博Garvin“
* 转载请标明出处:http://blog.csdn.net/buptgshengod
******************************************/
