接雨水怎样用双指针做到 O(1) 空间？

简答

接雨水是给一排宽度为 1 的柱子高度，问下雨后能存多少水。看单根柱子就好想：它上方的水面高度，取决于它左边最高的柱子和右边最高的柱子里较矮的那一根，水面减去它自己的高度就是这一格的水，结果小于 0 时按 0 算。

最直接的做法是先从左往右扫一遍，记下每个位置左边的最高值，再从右往左扫一遍记下右边的最高值，最后逐个结算，时间 O(n)、空间 O(n)。双指针把这两个数组省掉了：左右指针从两头往中间走，分别维护 leftMax 和 rightMax，哪边的最高值更矮，就结算哪边的指针并往里挪。

这样做成立，是因为如果 leftMax 比 rightMax 矮，左指针这一格的右边至少有一根 rightMax 那么高的柱子，所以它的水位只由 leftMax 决定，不用知道右边的完整情况。每个位置只结算一次，时间 O(n)，空间 O(1)。

要注意，这题和《双指针有哪些常见题型？》里的盛水最多的容器不同，那题只选两根柱子，中间的柱子不挡水；接雨水每一格都要算。单调栈也能做，它按“一层一层横着填”的方式算，同样 O(n)。

双指针写法

看 leftMax < rightMax 时为什么只结算左边。

JavaScript

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

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5])); // 9
console.log(trap([3, 2, 1])); // 0
console.log(trap([2, 0, 2])); // 2
console.log(trap([5])); // 0

为什么 leftMax - height[left] 不会是负数？因为每次结算前先用当前柱子更新了 leftMax，leftMax 至少等于这根柱子的高度，柱子比两边都高时结果就是 0，表示它上面存不了水。

为什么哪边矮就结算哪边？假设 leftMax < rightMax。左指针这一格左边的最高值就是 leftMax，这是确定的。右边的最高值我们还不完全知道，可是右指针那一侧已经出现过 rightMax，所以右边的最高值不会低于 rightMax，也就比 leftMax 高。两边取较矮的，结果一定是 leftMax。反过来 leftMax >= rightMax 时，同样的道理可以结算右边。

[3, 2, 1] 越往右越矮，水全都流走了，结果是 0。[2, 0, 2] 中间那格两边都是 2，存 2 格水。

单调栈怎么想

单调栈是栈里的元素保持单调递减。从左往右扫，栈里存下标，当前柱子比栈顶高时，说明栈顶那根柱子成了一个“坑底”，左边是栈里的下一个元素，右边是当前柱子。弹出坑底，用两边较矮的高度减去坑底高度，乘以两边之间的宽度，就是这一层能填的水，然后继续和新的栈顶比较。每个下标入栈出栈各一次，时间 O(n)，栈最多 O(n)。

JavaScript

function trapByStack(height) {
  const stack = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop();
      if (!stack.length) break;
      const left = stack[stack.length - 1];
      const level = Math.min(height[left], height[i]) - height[bottom];
      water += level * (i - left - 1);
    }
    stack.push(i);
  }
  return water;
}

console.log(trapByStack([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trapByStack([4, 2, 0, 3, 2, 5])); // 9

弹出坑底后栈空了，说明坑的左边没有挡板，水会流走，所以直接 break。双指针按列竖着算，单调栈按层横着算，两种方法加起来的总量一样。

常见追问

为什么循环条件是 left <= right？

每一格都要结算一次。两个指针相遇的那一格还没算过，用 <= 才会处理它。那一格通常是最高的柱子，结算出来是 0，所以写成 < 一般也能得到同样的答案，但 <= 的含义更清楚。

二维的接雨水怎么做？

给的是一个高度矩阵，水可以往四个方向流。做法是把最外一圈放进最小堆，每次取出最矮的边界，向四周扩展，比它矮的格子能存的水就是它们的高度差。这和一维双指针“从矮的一边先结算”是同一个思路。