题目描述

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

样例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

算法1

(单调栈) $O(n)$

对于每个位置，都需要寻找其左边右边第一个比自己高的位置，是使用单调栈的场合；
使用一个栈来存储idx，遍历数组将idx压入，并保证栈内idx访问到的高度是单调递减的；
一旦遇到某个idx高度比栈顶idx高，说明栈顶idx是一个凹槽处，栈顶idx右边第一个比它高的idx就是当前访问到的idx；
弹出当前栈顶，新栈顶即为旧栈顶idx左边第一个比它高的idx，找到了左右边界，便能以此计算、更新雨水量了；
不断弹出栈顶并更新雨水量，直到能够保证当前idx入栈后，栈内idx的高度可以保证单调递减，那么将它压入栈，并继续后续运算。

时间复杂度

每个元素最多进栈出栈一次，故时间复杂度为$O(n)$。

空间复杂度

最坏情况，所有元素入栈，空间复杂度为$O(n)$。

参考文献

C++ 代码

class Solution {
public:
    int trap(vector<int>& h) {
        if (h.empty()) return 0;
        h.push_back(0);
        stack<int> stk;
        int res = 0, n = h.size();

        for (int i = 0; i < n; ++i){
            // 一旦当前idx比栈顶idx的高度高，就去寻找另一边比栈顶高的idx,直到恢复栈中idx的单调递减
            while (stk.size() && h[stk.top()] < h[i]){ 
                int mid = h[stk.top()]; stk.pop();
                if (stk.empty()) break;
                res += (i - 1 - stk.top()) * (min(h[i], h[stk.top()]) - mid);
            }
            stk.push(i);
        }

        return res;
    }
};

算法2

(双指针) $O(n)$

空间复杂度$O(1)$的做法。
一个位置的储水只取决于左右比它大的高度，并且是由矮的那边决定的；
初始化时，将左右指针放在最左边、最右边；
每次移动高度较矮的那个指针，因为它是瓶颈；
如果移动后的高度变高了，那么当前位置必然储不了水了，更新边界高度；
如果移动后的高度变矮了，那么当前位置可以储水，并且储存高度就取决于其左右边界高度，计算一下储水量，更新答案。

时间复杂度

双指针总共遍历数组一次，故时间复杂度为$O(n)$。

空间复杂度

双指针的空间复杂度为$O(1)$。

参考文献

C++ 代码

class Solution {
public:
    int trap(vector<int>& h) {
        if (h.empty()) return 0;
        int n = h.size(), lh = h[0], rh = h[n - 1], l = 0, r = n - 1, res = 0;

        while (l <= r){
            if (lh <= rh){
                if (h[l] >= lh) lh = h[l];
                else res += lh - h[l];
                ++l;
            }

            else{
                if (h[r] >= rh) rh = h[r];
                else res += rh - h[r];
                --r;
            }
        } 

        return res;
    }
};