84.柱状图中最大的矩形

柱状图中最大的矩形

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

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

示例 1：

输入：heights = [2,1,5,6,2,3]
输出：10

示例 2：

输入：heights = [2,4]
输出：4

提示：

• 1 <= heights.length <= $10^5$
• 0 <= heights[i] <= $10^4$

解析

单调栈：维护一个递增栈，当遇到比栈顶小的元素时，弹出栈顶并计算以栈顶高度为矮边的矩形面积。

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
  const stack = []; // 存储下标
  let maxArea = 0;
  heights.push(0); // 末尾加 0，确保所有柱子都会被弹出

  for (let i = 0; i < heights.length; i++) {
    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
      const h = heights[stack.pop()];
      const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }

  heights.pop(); // 恢复原数组
  return maxArea;
};

单调栈解法的时间复杂度 O(n)，每个元素最多入栈出栈各一次。