柱状图中最大的矩形

[louzhedong]

习题

出处：LeetCode 算法第84题

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

解答

var largestRectangleArea = function (heights) {
  heights.push(0);
  var max = 0;
  var stack = [[0, -1]];
  var top = 0;
  heights.forEach(function (height, index) {
    var current = index;
    while (stack[top][0] > height) {
      var [h, i] = stack.pop();
      max = Math.max(max, (index - i) * h)
      current = i;
      top--;
    }
    if (stack[top][0] < height) {
      stack.push([height, current]);
      top++;
    }
  })
  return max;
};

Ï