42. 接雨水

 1 //自底向上层层叠加
 2 class Solution 
 3 {
 4 public:
 5     int trap(vector<int>& height) 
 6     {
 7         int res = 0;
 8         stack<int> stk;
 9 
10         for(int i = 0;i < height.size();i ++)
11         {
12             int last = 0;
13             while(stk.size() && height[stk.top()] <= height[i])
14             {
15                 int t = stk.top();
16                 stk.pop();
17 
18                 res += (i - t - 1) * (height[t] - last);
19                 cout << res << " ";
20                 last = height[t];
21             }
22 
23             if(stk.size())
24             {
25                 res += (i - stk.top() - 1) * (height[i] - last);
26             }
27             cout << res << " ";
28             stk.push(i);
29             cout << endl;
30         }
31         return res;
32     }
33 };