接雨水

分析

要解答这题，首先要明确什么情况下可以接到雨水。 从题目给出的示意图不难看出：只有当当前位置左右两侧都存在更高的挡板时，该位置才可能积水。 因此，我们可以参照 135 题那样的办法，通过前后两次遍历来解决。 首先，我们从左往右遍历，记录每个位置的最大高度 max(height[i], max_left[i-1])。 然后，我们再从右往左遍历，记录每个位置的最大高度 max(height[i], max_right[i+1])。 最后，我们取两侧最大高度的较小值，从而计算出每个位置可以接到的雨水，即 min(max_left[i], max_right[i]) - height[i]。

我们也可以使用单调栈的方法来解决这个问题。 在此题中，我们用单调栈存储下标。 当遍历到下标 i 时，我们做以下判断：

  • 如果当前柱子高度不高于栈顶柱子，则直接将 i 压入栈。
  • 如果当前柱子高于栈顶柱子，说明此时一个储水区域已经形成。这时：
    • 栈顶元素 top 为区域底部。
    • 当前元素 i 为区域右墙。
    • top 出栈的栈顶元素 left 为区域左墙。

因此，该区域的宽度为 i−left−1\mathrm{i} - \mathrm{left} - 1， 高度为 min⁡(height[left],height[i])−height[top]\min{(\mathrm{height}[\mathrm{left}], \mathrm{height}[\mathrm{i}])} - \mathrm{height}[\mathrm{top}]。 由于右墙 i 可能为递增序列，因此我们需要重复出栈和计算的过程。 直到该单调栈为空或者找到一个低于当前右墙高度的柱子为止。

同 135 题一样，我们也可以在两次遍历的基础上使用双指针进行优化。 经过观察，不难发现某个位置能接到的雨水取决于其左侧最高挡板和右侧最高挡板中的较小值。 我们可以将这两个数组优化为指针，并分别设置两个变量记录当前两侧的最大高度。 随后，两个指针分别从最左侧或最右侧开始向中间遍历。 此时有：

  • height[left]<height[right]\mathrm{height}[\mathrm{left}]<\mathrm{height}[\mathrm{right}]。 此时可以优先确定 left 位置的积水量，因此 left 处能接到的雨水为 max_left - height[left]。 并将 left 向右移动。
  • height[left]≥height[right]\mathrm{height}[\mathrm{left}]\ge\mathrm{height}[\mathrm{right}]。 此时可以优先确定 right 位置的积水量，因此 right 处能接到的雨水为 max_right - height[right]。 并将 right 向左移动。

当两个指针相遇时，即可得到最终结果。

解答

class Solution {
public:
  int trap(vector<int> &height) {
    auto ans = 0, left = 0, max_left = 0, max_right = 0;
    int right = height.size() - 1;


    while (left < right) {
      max_left = max(max_left, height[left]);
      max_right = max(max_right, height[right]);


      ans += height[left] < height[right] ? max_left - height[left++]
                                          : max_right - height[right--];
    }


    return ans;
  }
};