求最大全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){
    if(map == null || map.length == 0 || map[0].length == 0) return 0;
    var maxArea = 0;
    var height = [];
    for(var k = 0; k < map[0].length; k++){
        height[k] = 0;
    }

    for(var i = 0; i < map.length; i++){
        for(var j = 0; j < map[0].length; j++){
            height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
        }
        maxArea = Math.max(maxMatrixFromBottom(height), maxArea);
    }
    return maxArea;
}

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

var map =[
    [1,1,1,1],
    [1,1,1,1],
    [1,0,0,0]
  ];
console.log(getMaxMatrix(map))