最大矩形: (85号)

var maximalRectangle = function (matrix) {
  let max = 0
  if (matrix.length === 0) {
    return 0
  }
  let heights = new Array(matrix[0].length)
  for (let r = 0; r < matrix.length; r++) {
    let row = matrix[r]
    for (let c = 0; c < row.length; c++) {
      let item = row[c]
      if (item === '1') {
        if (heights[c]) {
          heights[c]++
        } else {
          heights[c] = 1
        }
      } else {
        heights[c] = 0
      }
    }
    max = Math.max(largestRectangleArea(heights), max)
  }
  return max
};

var largestRectangleArea = function (heights) {
  const stack = []
  let max = 0
  let i = 0
  while (i < heights.length) {
    if (stack.length === 0) {
      stack.push(i)
      i++
    } else {
      let topIndex = stack[stack.length - 1]
      let cur = heights[i]
      // 如果当前元素高 大于等于 栈顶元素的高; 直接入栈, 否则需要计算面积
      if (cur >= heights[topIndex]) {
        stack.push(i)
        i++
      } else {
        // 拿到栈顶元素, 同时将栈顶的元素 pop 出栈
        let topH = heights[stack.pop()]
        // 查看新栈顶下标的
        let newTop = stack.length === 0 ? -1 : stack[stack.length - 1]
        // 当前的 下标 i
        let area = (i - newTop - 1) * topH
        max = Math.max(max, area)
      }
    }
  }
  while (stack.length !== 0) {
    let topH = heights[stack.pop()]
    let newTop = stack.length === 0 ? -1 : stack[stack.length - 1]
    let w = heights.length
    let area = (w - (newTop + 1)) * topH
    max = Math.max(max, area)
  }
  return max
};

const r = maximalRectangle([
  ["1", "0", "1", "0", "0"],
  ["1", "0", "1", "1", "1"],
  ["1", "1", "1", "1", "1"],
  ["1", "0", "0", "1", "0"]
])

console.log(r)