求最大全1子矩阵中1的个数

Question

给定一个01矩阵map，求其中全是1的子矩阵里1的最大个数。
例如：

1 1 1 0

其中最大的全1子矩阵有3个1，返回3.

1 0 1 1
1 1 1 1
1 1 1 0
其中最大的全1子矩阵有6个1，返回6.

对于N*M的01矩阵，求时间复杂度为O(N*M)的Javascript实现方案

Answer 1

function getMaxMatrix(map){&nbsp; &nbsp; if(map == null || map.length == 0 || map[0].length == 0) return 0;&nbsp; &nbsp; var maxArea = 0;&nbsp; &nbsp; var height = [];&nbsp; &nbsp; for(var k = 0; k < map[0].length; k++){&nbsp; &nbsp; &nbsp; &nbsp; height[k] = 0;&nbsp; &nbsp; }&nbsp; &nbsp; for(var i = 0; i < map.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; for(var j = 0; j < map[0].length; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; height[j] = map[i][j] == 0 ? 0 : height[j] + 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; maxArea = Math.max(maxMatrixFromBottom(height), maxArea);&nbsp; &nbsp; }&nbsp; &nbsp; return maxArea;}function maxMatrixFromBottom(height){&nbsp; &nbsp; if(height == null || height.length == 0) return 0;&nbsp; &nbsp; var maxArea = 0;&nbsp; &nbsp; var stack = [];&nbsp; &nbsp; for(var i = 0; i < height.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; while(stack.length != 0 && height[i] <= height[stack[stack.length - 1]]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var j = stack.pop();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var k = stack.length == 0 ? -1 : stack[stack.length - 1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var curArea = (i - k -1) * height[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxArea = Math.max(maxArea, curArea);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; stack.push(i);&nbsp; &nbsp; }&nbsp; &nbsp; while(stack.length != 0){&nbsp; &nbsp; &nbsp; &nbsp; var j = stack.pop();&nbsp; &nbsp; &nbsp; &nbsp; var k = stack.length == 0 ? -1 : stack[stack.length - 1];&nbsp; &nbsp; &nbsp; &nbsp; var curArea = (i - k -1) * height[j];&nbsp; &nbsp; &nbsp; &nbsp; maxArea = Math.max(maxArea, curArea);&nbsp; &nbsp; }&nbsp; &nbsp; return maxArea;}var map =[&nbsp; &nbsp; [1,1,1,1],&nbsp; &nbsp; [1,1,1,1],&nbsp; &nbsp; [1,0,0,0]&nbsp; ];console.log(getMaxMatrix(map))