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

Question

给定一个01矩阵map，求其中全是1的子矩阵里1的最大个数。例如：1 1 1 0其中最大的全1子矩阵有3个1，返回3.1 0 1 11 1 1 11 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))