本文共 2079 字，大约阅读时间需要 6 分钟。
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 01 0 1 1 11 1 1 1 11 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 11 1 1 0 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 0 1We get:1 1 1 1 1 11 4 4 0 1 41 4 9 1 1 41 4 9 4 4 41 4 9 9 9 91 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“
* 转载请标明出处:
******************************************/