Description

算法步骤

暴力解法

• 枚举每个柱子，假设当前柱子是构成一个矩形的高度，不断向左右扩展寻找宽度。开始时，我们让l=i-1，r=i+1。
  • 如果每次观察到l所在位置的高度>=枚举到的高度，那么l往左跑一步
  • 如果每次观察到r所在位置的高度>=枚举到的高度，那么r往右跑一步
• 当l和r都跑到不符合条件后，则width = (r-1) - (l+1) + 1，计算当前围的矩形面积，更新最大矩形面积。

单调栈解法

暴力做法的本质是：向左跑找第一个小于当前柱子高度的位置，向右跑找第一个小于当前柱子高度的位置。那么如果我们枚举hs[i]的时候，能够迅速知道hs[i]的左右两边第一个小于hs[i]的位置，那么我们就可以获取hs[i]对应的矩形的宽度了从而计算矩形面积了。于是问题转化成了两个子问题：

• 找hs[i]的右边第一个小于hs[i]的位置。
• 找hs[i]的左边第一个小于hs[i]的位置。 因此我们想到可以使用单调栈来处理这两个子问题。我们维护一个从栈底到栈顶单调递增栈，栈中存储的是柱子的下标：
• 当栈空的时候我们直接放入当前柱子。
• 当栈不为空的时候，为了维持栈底到栈顶的单调递增的顺序，我们需要在柱子入栈时，不断比较栈顶和入栈柱子的高度。如果入栈柱子的高度比当前栈顶柱子的高度小，需要弹出栈顶柱子，否则无法维持单调递增的顺序。
• 弹出栈顶柱子之后，我们再将枚举的柱子入栈。
• 在弹出的过程当中，我们就可以结算，因为我们我找到了放在单调递增栈中的柱子右边第一个比它小的柱子。
• 同理，我们从右往左遍历，也可以找到左边第一个比它小的柱子。
• 最后的做法跟暴力解法一致，通过左右边界计算宽度，进而计算当前围的矩形面积，更新最大矩形面积。相对于暴力解法，我们相当于预处理了当前柱子的左右边界。

总结

找第一个更大/更小的元素，可以考虑使用单调栈，从栈底到栈顶的顺序：

• 找第一个比当前元素小的元素，可以考虑使用单调递增栈（84.柱状图中最大的矩形）。
• 找第一个比当前元素大的元素，可以考虑使用单调递减栈（739.每日温度）。

// 单调栈解法
function largestRectangleArea(hs: number[]): number {
  const n = hs.length;
  let st: number[] = [];
  const lSt: number[] = new Array(n).fill(-1);
  const rSt: number[] = new Array(n).fill(n);

  // 找每个数右边第一个比它小的位置
  for (let i = 0; i < n; i++) {
    while (st.length && hs[st[st.length - 1]] > hs[i]) {
      const j = st.pop()!;
      rSt[j] = i;
    }

    // 如果栈为空，说明左边没有比它小的位置
    if (st.length !== 0) {
      lSt[i] = st[st.length - 1];
    }

    st.push(i);
  }

  // 至此我们找到了所有柱子左边第一个比它小的位置，右边第一个比它大的位置。
  // 我们开始计算面积
  // 相对于暴力，我们相当于预处理了当前柱子的左右边界
  let ans = hs[0];
  for (let i = 0; i < n; i++) {
    let l = lSt[i];
    let r = rSt[i];

    const w = (r - 1) - (l + 1) + 1;
    const h = hs[i];
    ans = Math.max(w * h, ans);
  }

  return ans;
};

// 暴力解法（超时）
function largestRectangleArea2(hs: number[]): number {
  const n = hs.length;
  let ans = hs[0];
  // 枚举当前高度，假设当前高度是构成一个矩形的高度，不断向左右扩展寻找宽度
  for (let i = 0; i < n; i++) {
    let l = i - 1;
    let r = i + 1;

    // 如果每次观察到l所在位置的高度>=枚举到的高度，那么l往左跑一步
    while (l >= 0 && hs[l] >= hs[i]) {
      l--;
    }

    // 如果每次观察到r所在位置的高度>=枚举到的高度，那么r往右跑一步
    while (r < n && hs[r] >= hs[i]) {
      r++;
    }

    // 当l和r都跑到不符合条件后，则width = (r-1) - (l+1) + 1
    ans = Math.max(((r - 1) - (l + 1) + 1) * hs[i], ans);
  }

  return ans;
};
Copy