给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路

  1. 暴力遍历，以 height[i] 作为高时计算相关矩形面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var largestRectangleArea = function (heights) {
  let result = 0
  for (let i = 0; i < heights.length; ++i) {
    const curVal = heights[i]
    let [left, right] = [i, i]
    while (left > 0 && heights[left - 1] >= curVal) {
      --left
    }
    while (right < heights.length - 1 && heights[right + 1] >= curVal) {
      ++right
    }
    result = Math.max(result, (right - left + 1) * curVal)
  }
  return result
}

性能较差，个别用例出现了超时的情况，算法需要优化。 使用 leftBound、rightBound 数组维护指定下标的左右边界，leftBound[i] + 1 为左边界，rightBound[i] - 1 为右边界

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
var 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
}