接雨水问题

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

上面是由数组 [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

方法1：

纵向来看，每列积水深度取决于左右极大值中的最小值，所以只需要求出所有的极大值点，然后逐列求解即可。

方法2：

横向来看，积水的前提是被黑色方块成对包裹，所以逐行遍历，将奇数和偶数个黑色方块看成是成对的括号，就可以用堆栈的方式求出每行中积水的体积。

方法3：

积水后的图形实际是先单调递增后单调递减的，且水位取决于极大值，所以可以通过从两侧夹逼的方式计算出每列的水位，然后减去黑色方块高度并累加（类似于方法1）。

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