题外话

这个算法是我参考的网上的一个讲解大神叫Edward Shi 的，觉得非常巧妙，所以特意分享在这里，o(1)的空间复杂度, o(n)的时间复杂度。

非常巧妙的two pointer算法，不过我仔细想了一下，觉得这么巧妙的算法如果不是以前做过，真的在面试当中第一次看到，应该临时想不出这种算法，所以我觉得wzc1995的算法1非常的重要，因为它相当于是一种过渡，就是你当下看到可以立马想到也可以在短时间内写出来的算法，而且非常符合人的思维方式，刷了很多题之后，觉得计算机的思维方式跟人来说有很大差别，乍一看可能还会觉得，诶，为什么这样就行得通呢？

然后我看了wzc1995的算法一之后，再来看这个算法，就会明白，哦，原来是因为这样啊。

算法

(two pointer) $O(n)$

一般情况下，如果按照人的思维方式的话，要看每一个位置可以蓄多少水，我们首先会看看，左边最高的柱子有多高（这里的左边最高还包括当前这个位置的，不是真的就是在左边的最高的柱子），右边的柱子最高的有多高，然后取他们两个当中的最小值，减去当前柱子的高度，就是这个位置可以蓄的水的量了。

为什么取两边的最高的柱子当中的最小值呢？因为一个桶能蓄多少水看短板（这里我们有两个板，一个长板，一个短板）对不对。wzc1995的算法一就是把左边的最高的柱子找出来，把右边的最高的柱子也找出来，然后再取最小值，就算是找到了短板了。

而这个two pointer的算法就是，为什么非要把两边的最高的柱子都找出来再找短板呢？我们直接找短板不就好了。
为什么这样行得通呢？
因为你想啊，左边一个值记录到当前位置为止左边最高的柱子，右边一个值记录到当前位置为止右边最高的柱子，假设我们知道右边这个最高的柱子比左边那个最高的柱子矮，那么在当前位置，这个比较矮的右边最高柱一定是当前位置的短板，为什么呢？因为这个右边最高柱已经比那个左边最高柱矮了，那么即便两个
pointer 中间还有没有走完的位置，当前位置的长板也大于等于那个没有走完的左边最高柱了。所以我们就证明了，这个比较矮的板是当前位置的短板，然后用短板值减去当前柱子的高度就是当前位置蓄水量了。

整个vector扫一遍就是o(n)时间复杂度，左边一个pointer，右边一个pointer,还有两个值分别记录左边最高柱、右边最高柱，还有一个值记录蓄水量。所以是o(1)空间复杂度。

时间复杂度分析：o(n)

C++ 代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        int l = 0, r = n - 1;
        int leftmost = height[l], rightmost = height[r];
        int res = 0;
        while (l <= r) {
            if (leftmost < rightmost) {
                res += leftmost - height[l++];
                leftmost = max(leftmost, height[l]);
            } else {
                res += rightmost - height[r--];
                rightmost = max(rightmost, height[r]);
            }
        }
        return res;
    }
};