大名鼎鼎的一道题，看讨论区居然有5 6种解法，令人尴尬的是我一种都没AC，看了大神的解题思路，自己较轻松的完成了代码。

暴力破解

暴力破解方法是后续所有解法的基础，如果理解不了暴力破解解法，那么后续所有解法将无法理解。

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

以上图为例，这里有个思维的转变，我们是一格一格的计算雨水存量，计算出当前格子左边最大高度和右边最大高度，两者较小值减去当前格子高度，就是当前格子能够保存的雨水量。代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0,size = height.size();
        for(int i = 1;i < height.size();i++)
        {
            int maxl = 0,maxr = 0;
            for(int j = i;j >=0;j--)
                maxl = max(maxl,height[j]);
            for(int j = i;j < size;j++)
                maxr = max(maxr,height[j]);
            ans += min(maxl,maxr) - height[i];
        }
        
        return ans;
    }
};

运行效率:

Runtime: 320 ms, faster than 5.09% of C++ online submissions for Trapping Rain Water.
Memory Usage: 14.1 MB, less than 95.35% of C++ online submissions for Trapping Rain Water.

动态规划

理解了上面的暴力破解方法，其实动态规划就相对好理解了，上面的暴力破解我们计算当前结点左边和右边最大高度放在外层循环中，导致时间复杂度为n的平方，因此可以按照上述方法可以提前求解出当前结点左边最大高度和右边最大高度。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(),max = 0,ans = 0;
        if(n <= 0) return 0;
        
        vector<int> left(n,height[0]),right(n,height[n-1]);
        
        for(int i = 1;i < height.size();i++)
        {
            left[i] = std::max(left[i-1],height[i]);
        }
        
        for(int i = n - 2;i >= 0;i--)
        {
            right[i] = std::max(right[i+1],height[i]);
        }
        
        for(int i = 1;i < n;i++)
        {
            ans += min(left[i],right[i]) - height[i];
        }
        
        return ans;
    }
};

运行结果:

Runtime: 8 ms, faster than 67.95% of C++ online submissions for Trapping Rain Water.
Memory Usage: 14.3 MB, less than 70.02% of C++ online submissions for Trapping Rain Water.

栈的应用

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0,curr = 0;
        stack<int> st;
        while(curr < height.size())
        {
            while(!st.empty() && height[curr]>height[st.top()])
            {
                int top = st.top();
                st.pop();
                if(st.empty()) break;
                int distance = curr - st.top() - 1;
                int bounded_height = min(height[curr], height[st.top()]) - height[top];
                ans += distance * bounded_height;
            }
            st.push(curr++);
        }
        
        return ans;
    }
};

运行效率:

Runtime: 12 ms, faster than 33.94% of C++ online submissions for Trapping Rain Water.
Memory Usage: 14.4 MB, less than 60.47% of C++ online submissions for Trapping Rain Water.