85. 最大矩形

[linqibin]

85. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

/**
 * @param {character[][]} matrix
 * @return {number}
 */
function maximalRectangle(matrix) {
    const temMatrix = [];
    let max = 0;

    for(let i = 0; i < matrix.length; i++){
        const row = [];
        temMatrix.push(row);
        for(let j = 0; j < matrix[i].length; j++){
            if(!i){
                row[j] = Number(matrix[i][j]);
            }else {
                if(matrix[i][j] == 0){
                    row[j] = 0;
                }else{
                    row[j] = Number(temMatrix[i - 1][j]) + Number(matrix[i][j]);
                }
            }
        }
    }
    
    for(let i = 0; i < temMatrix.length; i++){
        const area = largestRectangleArea(temMatrix[i]);
        if(area > max){
            max = area;
        }
    }

    return max;
};

function largestRectangleArea(heights) {

    if (heights.length == 0)
        return 0;
    else if (heights.length == 1) {
        return heights[0];
    }

    const stack = [0];
    let max = heights[0];
    heights.push(0);

    for (let i = 1; i < heights.length; i++) {
        const area = getArea(i);
        stack.push(i);
        
        if(area > max){
            max = area;
        }
    }

    return max;

    function getArea(currentIndex) {
        let maxArea = 0;
        const current = heights[currentIndex];

        while (stack.length && current < heights[stack[stack.length - 1]]) {
            let index = stack.pop();
            let height = heights[index];

            let length = stack.length ? currentIndex - stack[stack.length - 1] - 1 : currentIndex;
            const area = height * length;  
            
            if(area > maxArea){
                maxArea = area;
            }
        }

        return maxArea;
    }
};