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.
1 /** 2 * @param {character[][]} matrix 3 * @return {number} 4 */ 5 var maximalSquare = function(matrix) { 6 if(matrix.length === 0) return 0; 7 var max = 0, i, j, dp = [], tmp, 8 height = matrix.length, width = matrix[0].length; 9 for(i = 0; i < height; i++) 10 dp[i] = []; 11 for(i = 0; i < height; i++){ 12 for(j = 0; j < width; j++){ 13 if(matrix[i][j] === ‘1‘){ 14 tmp = getSquare(i, j); 15 dp[i][j] = tmp; 16 max = Math.max(max, dp[i][j]); 17 } 18 } 19 } 20 return max * max; 21 22 function getSquare(i, j){ 23 if(!matrix[i - 1] || !matrix[i - 1][j - 1]) 24 return 1; 25 var index, width = dp[i - 1][j - 1]; 26 if(!width) return 1; 27 for(index = 1; index <= width; index++) 28 if(!matrix[i - index] || matrix[i - index][j] !== ‘1‘ 29 || matrix[i][j - index] !== ‘1‘) 30 return index; 31 return width + 1; 32 } 33 };
[LeetCode][JavaScript]Maximal Square
原文:http://www.cnblogs.com/Liok3187/p/5225665.html