算法一：动态规划法
dp[i]表示当前位置能接多少单位的水
dp[i]的存水量是i最左边和最高高度lmax和最右边的最高的高度lmax中的相对低的一个的高度再减去当前i的高度
所以使用一个lmax数组和rmax数组来预处理i左边的最大高度和右边的最大高度

class Solution {
public:
    int trap(vector<int>& h) {
        int n = h.size();
        vector<int> l(n), r(n);
        l[0] = h[0], r[n - 1] = h[n - 1];
        for(int i = 1; i < n; i ++)
            l[i] = max(l[i - 1], h[i]);
        for(int i = n - 2; i >= 0; i --)
        {
            r[i] = max(r[i + 1], h[i]);
        }
        int res = 0;
        for(int i = 0; i < n; i ++)
        {
            res += min(l[i], r[i]) - h[i];
        }
        return res;
    }
};

算法二：单调栈
维护一个单调递减栈， 当遇到第一个递增的h[i]时， 那么一定是可以蓄水的，栈顶元素h[top]的前一个元素充当左边界，h[i]充当右边界，蓄水量就是左右边界中间的体积减去柱子的高度

class Solution {
public:
    int trap(vector<int>& h) {
       stack<int> sk;
       int n = h.size();
       int i = 0, res = 0;
       while(i < n)
       {
           while(sk.size() && h[i] > h[sk.top()])
           {
                int top = sk.top();
                sk.pop();
                if(sk.empty())break;
                int l = sk.top();
                int width = i - l - 1;//宽度
                int length = min(h[l], h[i]) - h[top];//高度
                res +=  length * width;
           }
           sk.push(i ++);
       }
       return res;
    }
};