85. 最大矩形 困难

问题：

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

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = [["0"]]
输出：0

示例 3：

输入：matrix = [["1"]]
输出：1

回答：

var maximalRectangle = function(matrix) {
    let row = matrix.length;
    let col = matrix[0].length;
    //维护一个单调栈，每列‘1’的高度
    let arr = new Array(col).fill(0);
    let maxArea = 0;
    //求矩形的最大面积
    var getLargestArea = function(arr) {
        var stack = [];
        let heights = [...arr, 0];
        let max = 0;
        for (let i = 0; i < heights.length; i++) {
            //维护一个递增的单调栈,存放索的引列
            while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
                let height = heights[stack.pop()]; //高度
                let width = stack.length == 0 ? i : i - stack[stack.length - 1] - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i)
        }
        return max;
    }
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (matrix[i][j] == '1') {
                arr[j] = arr[j] + 1;
            } else {
                arr[j] = 0;
            }
        }
        maxArea = Math.max(maxArea, getLargestArea(arr))
    }
    return maxArea;
};