85.最大矩形——hard-单调栈

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

输入:
[
[“1”,”0”,”1”,”0”,”0”],
[“1”,”0”,”1”,”1”,”1”],
[“1”,”1”,”1”,”1”,”1”],
[“1”,”0”,”0”,”1”,”0”]
]
输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle

思路：
利用
84.柱状图中最大的矩形——hard-单调栈
中提到的单调栈思路， ,对每一行的high求一个最大矩形即是答案。
复杂度分析：
时间复杂度O(nm) 对每一行运行 需要 n (每行长度) 时间，运行了 m 次，共计 O(nm)。
空间复杂度O(n)

var maximalRectangle = function(matrix) {
    if(!matrix||!matrix.length||!matrix[0].length) return 0;
    let m=matrix.length;
    let n=matrix[0].length;
    let high = new Array(n).fill(0);
    let maxArea=0;
    let getMaxArea= (row)=>{
        row= [-1,...row,-1]
        let maxStack=[];
        for(let i=0;i<row.length;i++){
           while(row[i]<row[maxStack[maxStack.length-1]]){
                let tmp=maxStack.pop()
                maxArea=Math.max(maxArea,row[tmp]*(i-maxStack[maxStack.length-1]-1))
            }
          maxStack.push(i)
        }
    }
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            let tmp=Number(matrix[i][j])
            if(i===0){
                high[j]=tmp
            }else{
                high[j]=tmp?tmp+high[j]:tmp
            }
        }
        getMaxArea(high)
    }
    return maxArea
};