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

输入：height = $[0,1,0,2,1,0,1,3,2,1,2,1][0,1,0,2,1,0,1,3,2,1,2,1]$

如图所示：

输出：6

如图所示：

由木桶效应，我们知道下雨之后，能接到的水由$min(height[i],height[k])min(height[i],height[k])$决定，如图所示：

故可以把上述问题转换成讨论往木桶填加不同高度木块，对木桶容量的改变。记木桶两端最小高度为 $heigh{t}_{min}height\_\{min\}$。

1.当加入一块木块$xx$,其高度满足 ，显然对木桶容量产生负作用，如图所示：

2.当加入一块木块$xx$,其高度满足 $heigh{t}_x>heigh{t}_{min}height\_\{x\}>height\_\{min\}$，显然增加了木桶容量，如图所示：

为了简化问题，遍历新产生的数组都从最低高度出发。

代码实现，如下所示：

#include <vector>
#include <iostream>
using namespace std;

int trap(vector<int>&);

int main(int argc, char* argv[]) {
    int num;
    while (cin >> num) {
        vector<int> height;
        for (int i = 0; i < num; i++) {
            int buf;
            cin >> buf;
            height.push_back(buf);
        }
        cout << trap(height) << endl;
    }
    return 0;
}

#define MAX(a, b) (a > b ? a : b)

int trap(vector<int>& height) {
    int left = 0, l_block = height[left];
    int right = height.size() - 1, r_block = height[right];
    
    int ans = 0;
    while (left < right) {
        if (l_block < r_block) {
            ans += l_block - height[left];
            left++;
            l_block = MAX(l_block, height[left]);
        } else {
            ans += r_block - height[right];
            right--;
            r_block = MAX(r_block, height[right]);
        }
    }
    return ans;
}