LeetCode Hot 100：接雨水 (2026)

本期讲 LeetCode Hot 100 的「接雨水」。题目给一个非负整数数组 height，每根柱子宽度为 1，要求计算下雨后能接住多少单位的水。官方示例里，[0,1,0,2,1,0,1,3,2,1,2,1] 的输出是 6，[4,2,0,3,2,5] 的输出是 9；约束为 1 <= n <= 2 * 10^4、0 <= height[i] <= 10^5。详见 LeetCode 42. Trapping Rain Water 和力扣 42. 接雨水。

这题考察的不是「模拟水怎么流」，而是把每个位置的水量改写成边界问题：当前位置能接的水，取决于左侧最高柱和右侧最高柱里的较小值。双指针写法的关键不变量是：当 leftMax < rightMax 时，左边这一格的右侧边界已经足够高，水量可以按 leftMax - height[left] 结算；反过来就结算右边。LeetCode 结构化题目数据给出的标签是 Array、Two Pointers、Dynamic Programming、Stack、Monotonic Stack；题面当前未列出 Follow-up。

function trap(height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let answer = 0;

while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);

if (leftMax < rightMax) {
      answer += leftMax - height[left];
      left++;
    } else {
      answer += rightMax - height[right];
      right--;
    }
  }

return answer;
}

时间复杂度是 O(n)，因为 left 和 right 最多各走一遍；额外空间复杂度是 O(1)。数组长度小于 3、单调递增、单调递减时都不会产生可累加的水量，代码会自然返回 0。

Related content