42. Trapping Rain Water

I don't have idea to solve this problem in first place. I followed the top voted solution. The idea is instead of computing the area by height * width we can do it in a cumulative way. We scan inner ward from the left and right ends. We alway focus on the lower height. If current left rectangle is higher than the right rectangle, then we can guarantee trapped water by the left rectangle and the maximum rectangle so far on right.

Case 1: left height is lower than the right height.
We focus on the left side. In the left side, we keep the highest height so far. If current height is less than the highest one, so the water trap for current position is (highest height - current height) (you can image two bars with one higher than the other). Otherwise, we update the highest height to current height and no water trap for current position.

Case 2: left height is higher than the right height.
We focus on the right side. Same idea with Case 1.

1:  class Solution {  
2:  public:  
3:    int trap(vector<int>& height) {  
4:      int maxLeftHeight = 0, maxRightHeight = 0;  
5:      int left = 0, right = height.size()-1;  
6:      int area = 0;  
7:      while (left <= right) {  
8:        if (height[left] <= height[right]) {  
9:          if (maxLeftHeight <= height[left]) maxLeftHeight = height[left];  
10:          else area += maxLeftHeight - height[left];  
11:          left++;  
12:        } else {  
13:          if (maxRightHeight <= height[right]) maxRightHeight = height[right];  
14:          else area += maxRightHeight - height[right];  
15:          right--;  
16:        }  
17:      }  
18:      return area;  
19:    }  
20:  };