[leetcode] Maximal Square

好吧。我是看了提示
就是每一格都是代表它所在的正方形的右下角...
可以表示为
size[i][j] = min(size[i-1][j-1], size[i][j-1], size[i-1][j])+1
implementation 可以直接用一个滚动数组instead of 2d Array

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

public class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null||matrix.length==0||matrix[0].length==0){ return 0; } int maxSquare = 0; int []row = new int[matrix[0].length]; for (int i = 0; i < matrix[0].length; i++){ row[i] = matrix[0][i] - '0'; maxSquare = Math.max(maxSquare, row[i]); } for (int i = 1; i < matrix.length; i++){ int temp = row[0]; row[0] = matrix[i][0] - '0'; for (int j = 1; j < matrix[0].length; j++){ int hold = row[j]; if (matrix[i][j] != '0'){ row[j] = Math.min(row[j], Math.min(row[j-1], temp))+1; maxSquare = Math.max(maxSquare, row[j]*row[j]); }else{ row[j] = 0; } temp = hold; } } return maxSquare; } }