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

思路

  1. 与 84 - 柱状图中最大的矩形 类似，矩阵每一行及其以上部分，可以视为是一个柱状图
  2. 因此可以在 largestRectangleArea 代码的基础上实现算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
var maximalRectangle = function (matrix) {
  const [M, N] = [matrix.length, matrix[0].length]
  const barMatrix = new Array(M + 1).fill(null).map(() => new Array(N).fill(0))
  for (let i = 0; i < M; ++i) {
    for (let j = 0; j < N; ++j) {
      if (matrix[i][j] !== '1') {
        continue
      }
      barMatrix[i + 1][j] = 1 + barMatrix[i][j]
    }
  }
  const largestRectangleArea = function (heights) {
    let result = 0
    const leftBound = new Array(heights.length).fill(0)
    const rightBound = new Array(heights.length).fill(0)
    {
      const stack = []
      for (let i = 0; i < heights.length; ++i) {
        while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
          stack.pop()
        }
        leftBound[i] = stack.length > 0 ? stack[stack.length - 1] : -1
        stack.push(i)
      }
    }
    {
      const stack = []
      for (let i = heights.length - 1; i >= 0; --i) {
        while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
          stack.pop()
        }
        rightBound[i] = stack.length > 0 ? stack[stack.length - 1] : heights.length
        stack.push(i)
      }
    }
    for (let i = 0; i < heights.length; ++i) {
      const curVal = heights[i]
      result = Math.max(result, (rightBound[i] - leftBound[i] - 1) * curVal)
    }
    return result
  }
  let result = 0
  for (let i = 1; i <= M; ++i) {
    result = Math.max(result, largestRectangleArea(barMatrix[i]))
  }
  return result
}