Description

算法步骤

1. 维护一个递减单调栈，存储柱子索引
2. 遍历每个柱子：
   • 当遇到比栈顶高的柱子时，说明找到了右边界
   • 弹出栈顶，计算接水量：宽度 × 高度
   • 宽度 = 右边界 - 左边界 - 1
   • 高度 = min(右边界高度, 左边界高度) - 当前柱子高度
3. 将当前柱子入栈

时间复杂度： O(n)
空间复杂度： O(n)

单调栈解法核心思想

1. 维护递减单调栈：栈中存储递减的柱子索引
2. 一行行填水：当遇到比栈顶高的柱子时，立即计算接水量
3. 横向计算：每次计算一层水的体积，就像填水泥一样

function trap(hs: number[]): number {
  const n = hs.length;
  let ans = 0;
  const st: number[] = [0]; // 维护递减单调栈，存储索引

  for (let i = 1; i < n; i++) {
    // 当遇到比栈顶高的柱子时，可以计算接水量
    while (st.length > 0 && hs[i] > hs[st[st.length - 1]]) {
      const top = st.pop()!;

      // 如果栈为空，说明左边没有更高的柱子，无法接水
      if (st.length === 0) {
        break;
      }

      // 计算接水量：宽度 * 高度
      const l = st[st.length - 1]; // 左边第一个比top高的柱子
      const w = i - l - 1; // 宽度
      const h = Math.min(hs[i], hs[l]) - hs[top]; // 高度

      ans += w * h;
    }

    st.push(i);
  }

  return ans;
}
Copy