[84] 柱状图中最大的矩形

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

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

示例 1:

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

输出：10

解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]

输出： 4

暴力求解

这道题需要我们求出柱状图中所包含的最大矩形面积。那么最直观的，我们遍历每一个柱子，并向右延伸，找到最矮的柱子的高度，并乘以当前遍历的左右宽度，就能得到当前的矩形面积。依次比较求出最值即可。

function largestRectangleArea(heights: number[]): number {
  let maxArea = 0;
  for (let i = 0; i < heights.length; i++) {
    let minHeight = heights[i];
    for (let j = i; j < heights.length; j++) {
      minHeight = Math.min(minHeight, heights[j]);

      maxArea = Math.max(maxArea, minHeight * (j - i + 1));
    }
  }
  return maxArea;
}

暴力求解优化

上面的做法显然时间复杂度会是 O(n^2)，是没办法通过 AC 的。我们需要通过优化来减少时间复杂度。

注意到，其实对于一个柱子，我们并不需要遍历所有的情况才能找出最大面积。我们可以换个思路，对于每一个柱子，我们找到以该柱子为最矮柱子所能向左右延伸的最大面积。

这样一来，我们就能找到，以每一个柱子为高的最大矩形面积，然后求出最大值即可。

function largestRectangleArea(heights: number[]): number {
  let maxArea = 0;
  for (let i = 0; i < heights.length; i++) {
    // 问题转换成，找到以第i根柱子为最矮柱子所能向左右延伸的最大面积
    const height = heights[i];
    let left = i;
    let right = i;
    while (left >= 0 && heights[left] >= height) {
      left -= 1;
    }
    while (right < heights.length && heights[right] >= height) {
      right += 1;
    }
    maxArea = Math.max(maxArea, height * (right - 1 - (left + 1) + 1));
  }
  return maxArea;
}

单调栈

上面虽然对暴力求解进行了优化，减少了很多重复的计算，但是仍然改变不了需要嵌套两次遍历柱状图，其最差时间复杂度依然是 O(n^2)。我们需要进一步优化。

既然时间复杂度是 O(n^2)，那么我们就需要考虑是否可以通过空间换时间，将时间复杂度降低到 O(n)。

在这里我们可以通过单调栈来解决这个问题。参考我们在496. 下一个更大元素 I中的单调栈算法，我们可以计算得出两个数组：分别代表当前元素的上一个和下一个更小元素的索引。

在获取这两个数组后，我们就可以通过这两个数组的每个元素差值来计算出以当前柱子为最矮柱子所能向左右延伸的最大面积。问题得解。

function largestRectangleArea(heights: number[]): number {
  let maxArea = 0;

  const len = heights.length;
  const resLeft: number[] = [];
  // 单调栈，时刻维护栈是递减状态的
  let stack: number[] = [];

  for (let i = 0; i < len; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
      stack.pop();
    }

    resLeft[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    stack.push(i);
  }

  stack = [];
  const resRight: number[] = [];
  for (let i = len - 1; i >= 0; i--) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
      stack.pop();
    }

    resRight[i] = stack.length === 0 ? heights.length : stack[stack.length - 1];
    stack.push(i);
  }

  for (let i = 0; i < len; i++) {
    const width = resRight[i] - resLeft[i] - 1;
    const height = heights[i];
    maxArea = Math.max(maxArea, height * width);
  }

  return maxArea;
}

单调栈优化

上面这个方法照搬单调栈公式获得了能够 AC 的正确结果，但我们仍然可以尝试进一步优化一下。

在上面的代码中，我们使用了两个单调栈，分别用来计算当前柱子的左右两侧的最小柱子的索引。但是我们可以通过一个单调栈来取得同样的结果。我们设这个单调栈为单调递增的 bar 的索引栈，这样我们就可以在遍历到某个 bar 时，遇到比栈顶矮的 bar 时，出栈栈顶并计算以该栈顶为高的最大矩形面积。

算法为：当前位置减去出栈后剩余栈顶的位置的差作为宽度，栈顶索引所对应的bar 作为高度，来求出以该栈顶为高的最大矩形面积。

这是因为，当我们遇到一个比栈顶矮的 bar A 时，我们可以确定,当前的 bar A 一定是栈顶 bar B 的右边第一个比它矮的 bar。而将该栈顶 bar B 出栈后，左边第一个比它矮的 bar，一定是剩余栈的栈顶 bar C。通过这样的方式，我们就能求出 bar B 的最大矩形的左右宽度。

最后我们来考虑一下边界问题。我们会遇到两种情况，第一种是，如果栈为空，我们是没法求得左边界的，因此我们需要在遍历前在头上加入一个 0。第二种是，当遍历结束后，栈中还有元素，我们需要将栈中的元素依次出栈，计算以该栈顶为高的最大矩形面积，因此我们需要尾部也加上 0，确保栈中所有非 0 元素都能正确出栈。

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let maxArea = 0;
  // 为什么前后加 0
  // 第一个加 0，因为求宽度时需要出栈后的栈顶参与计算，所以栈永远不能为空
  // 最后一个加 0，是为了让还在栈中的所有非 0 bar 都能依次出栈
  const newHeights = [0, ...heights, 0];

  for (let i = 0; i < newHeights.length; i++) {
    // 维持单调递增栈
    // 遇到了当前 bar 比栈顶矮的情况，出栈并计算以该栈顶为高的最大矩形面积
    while (stack.length > 0 && newHeights[i] < newHeights[stack[stack.length - 1]]) {
      const stackPopIndex = stack.pop();
      const curHeight = newHeights[stackPopIndex];
      const curWidth = i - 1 - stack[stack.length - 1];
      maxArea = Math.max(maxArea, curHeight > curWidth);
    }

    // 当前 bar 比栈顶高，将索引入栈，维持单调递增栈的索引正确
    stack.push(i);
  }
  return maxArea;
}