#### 暴力破解

``````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.``````

#### 动态规划

``````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.``````