Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

``````Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

^
3|              ■           □: water
2|      ■ □ □ □ ■ ■ □ ■     ■: elevation map
1|  ■ □ ■ ■ □ ■ ■ ■ ■ ■ ■
————————————————————————>
The above elevation map 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.
``````

`````` 1 class Solution
2 {
3 public:
4     int trap(int A[], int n)
5     {
6         int res = 0, l = 0, r = n - 1;
7
8         while(l < r)
9         {
10             int minh = min(A[l], A[r]);
11             if(A[l] == minh)
12                 while(++ l < r && A[l] < minh)
13                     res += minh - A[l];
14             else
15                 while(l < -- r && A[r] < minh)
16                     res += minh - A[r];
17         }
18
19         return res;
20     }
21 };``````