接雨水

单调栈如何计算接雨水量？

• 定位 (42): 需要为每根柱子找到左、右两侧第一个更高的柱子, 正是单调栈的两侧查询;
• 角色: 栈顶定义为凹槽底部 B, 当前柱体 C 是 B 右侧第一个更高者, B 弹出后的新栈顶 A 是左侧第一个更高者;
• 水量: 深度为 min(height[A], height[C]) - height[B], 宽度为 A 与 C 之间 (不含两端) 的下标跨度;
• 收尾: 栈空说明 B 左侧没有边界, 该凹槽不蓄水;

const trap = (height) => {
  let res = 0;
  const stack = [];
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack.at(-1)]) {
      const mid = stack.pop();
      if (stack.length === 0) break;
      const left = stack.at(-1);
      const depth = Math.min(height[left], height[i]) - height[mid];
      res += depth * (i - left - 1);
    }
    stack.push(i);
  }
  return res;
};

• 时间 $O(n)$, 空间 $O(n)$;

双指针法为什么不需要额外空间？

• 前提: 每根柱子的蓄水量只取决于 min(左侧最高, 右侧最高) - 自身高度;
• 做法: 左右指针从两端向中间收, 每次移动较矮一侧, 并把该侧已知最高更新为当前边界;
• 正确性: 较矮一侧的边界已经确定, 因为另一侧只会更高;
• 时间 $O(n)$, 空间 $O(1)$;

const trapWithTwoPointers = (height) => {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let res = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      res += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      res += rightMax - height[right];
      right--;
    }
  }
  return res;
};