85. Maximal Rectangle（js）

85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6
题意：在所给的二维数组中，求所有1组成的矩形的最大面积
代码如下：

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
   if (matrix.length === 0) {
        return 0
    }
    const heights = new Array(matrix[0].length + 1).fill(0)
    let ret = 0
    matrix.forEach(line => {
        line.forEach((flag, i) => {
            heights[i] = flag === '1' ? heights[i] + 1 : 0
        })
        const stack = [[0, -1]]
        let top = 0
        heights.forEach((height, index) => {
            let memoIndex = index
            while (stack[top][0] > height) {
                const [h, i] = stack.pop()
                ret = Math.max(ret, (index - i) * h)
                memoIndex = i
                top--
            }
            if (stack[top][0] < height) {
                stack.push([height, memoIndex])
                top++
            }
        })
    })
    return ret
}