题目：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

解法一：暴力

逐个计算每一列能存下的水量。

遍历整个数组。针对数组中的每个元素arr[i]，都分别向左、向右遍历一遍数组，找到arr[i]左侧和右侧的最大值，计为leftMax和rightMax，如果leftMax <= arr[i]或者rightMax <= arr[i]，说明当前这一列存不出水。否则当前列能存储的水量为min(leftMax, rightMax) - arr[i]。

所以数组的i位置能存储的水量res[i] = max{0, min{max(arr[0...i-1]), max(arr[i+1...n])} - arr[i] }。

再思考一下，如果max(arr[0...i-1]) > arr[i]，那么数组0到i-1位置的最大值和0到i位置的最大值一定是相等的；如果max(arr[0...i-1]) <= arr[i]，那么数组0到i位置的最大值一定等于arr[i]，所以为了避免和0之间取max的计算，上述公式可以化简为下面的形式。
res[i] = min{max{arr[0... i]} , max{arr[i . . . n − 1]}} − arr[i]

int trap(vector<int>& height) {
    int sum = 0;
    int n = height.size();
    for (int i=0; i<n; i++) {
        int leftMax = 0;
        for (int j=0; j<=i; j++) {
            if (height[j] > leftMax) {
                leftMax = height[j];
            }
        }
        int rightMax = 0;
        for (int j=i; j<n; j++) {
            if (height[j] > rightMax) {
                rightMax = height[j];
            }
        }
        sum += min(leftMax, rightMax) - height[i];
    }
    return sum;

}

解法二：双指针

从暴力解法中我们可以看到，要求数组i位置可以存储的水量，需要先求出0到i位置的最大值max(arr[0...i])，再求出i到n-1位置的最大值max(arr[i...n-1])，两个值中取最小与arr[i]做差。

暴力解法之所以时间复杂度比较差，是因为对于数组中的每一个元素，都需要再遍历一遍数组才能得到它左右两侧的最大值。

所以我们可以通过预处理数组得到leftMax[]和rightMax[]两个数组，leftMax[i]代表数组0到i位置的最大值，leftMax[i] = max(leftMax[i-1], arr[i])；rightMax[i]代表数组i位置到n-1位置的最大值，rightMax[i] = max(rightMax[i+1], arr[i])。

这样我们就得到了如下的算法流程。

首先遍历数组，从左向右得到数组leftMax[]，再从右向左得到rightMax[]。然后再遍历一遍数组，对于数组的每一个位置i，通过leftMax[i]，rightMax[i]和arr[i]得到结果，将结果汇总得到的值就是最终答案。

int trap(vector<int>& height) {
    int n = height.size();
    vector<int> leftMax(n, 0);
    leftMax[0] = height[0];
    for (int i=1; i<n; i++) {
        leftMax[i] = max(leftMax[i-1], height[i]);
    }

    vector<int> rightMax(n, 0);
    rightMax[n-1] = height[n-1];
    for (int i=n-2; i>=0; i--) {
        rightMax[i] = max(rightMax[i+1], height[i]);
    }

    int res = 0;
    for (int i=0; i<n; i++) {
        res += min(leftMax[i], rightMax[i]) - height[i];
    }
    return res;

}

解法三：双指针进阶

解法二中的双指针需要遍历三次数组，第一次得出数组leftMax[]，第二次得出数组rightMax[]，第三次才是根据leftMax[i]，rightMax[i]和height[i]得出结果。那我们能不能想办法把这三次遍历合并成一次呢？

我们设置两个指针，left指向数组的0位置，right指针指向数组的n-1位置。再使用两个变量leftMax和rightMax，leftMax的含义是数组0...left位置的最大值，rightMax的含义是数组right...n-1位置的最大值，这几个变量设置好后就有以下几种情况。

  • leftMax < rightMax，此时可以使用leftMax来结算height[left]位置的储水量。它的右侧可能还会有比rightMax更高的元素，但不会影响left位置的储水量。因为这种情况下left位置左侧的最大值是影响该位置储水量的瓶颈，此时res[left] = leftMax - height[left]。
  • leftMax > rightMax，此时可以使用rightMax来结算right位置的储水量。同样的，它的左侧可能还会有比leftMax更高的元素，但都不影响right位置的储水量。因为这种情况下right位置右侧的最大值是影响该位置储水量的瓶颈。此时res[right] = rightMax - height[right]。
  • leftMax == rightMax，此时既可以结算左侧，也可以结算右侧，或者左右两侧可以同时结算储水量。res[left] = leftMax - height[left]，res[right] = rightMax - height[right]。但是要注意如果结算前left == right，此时只能结算一侧。

不断重复上述流程，哪侧结算就将哪侧的指针相应移动，并在移动的过程中更新leftMax和rightMax，直到两个指针会合，结算完最后一个位置的水量为止。

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int leftMax = 0;
        int rightMax = 0;
        int res = 0;
        while (left <= right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (leftMax < rightMax) {
                res += leftMax - height[left++];
            }
            else if (leftMax >= rightMax) {
                res += rightMax - height[right--];
            }
        }
        return res;
    }
};