LeetCode --- 42. Trapping Rain Water

LeetCode --- 42. Trapping Rain Water

題目鏈接：Trapping Rain Water

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. 

這道題的要求是計算最多能裝多少水。其中，數組中的數字表示高度。

這道題的思路是采用l和r兩個指針，維護裝水兩邊的位置。

當l處高度低時，說明l右側裝的水肯定和l處一樣高，此時逐步右移l，同是加上l處與右移後位置高度差（因為這裡都能裝水啊），直到再遇到同樣高或者更高的位置。然後進行下一輪判斷。

同樣，當r處高度低時，說明r左側的水肯定和r處一樣高，此時逐步左移r，同是加上r處與左移後位置高度差，直到再遇到同樣高或者更高的位置。

最後直到l和r相遇，結束。

時間復雜度：O(n)

空間復雜度：O(1)

 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 };