## Sunday, November 16, 2014

### [LeetCode] 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`.
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. Thanks Marcos for contributing this image!

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25``` ```class Solution { public: int trap(int A[], int n) { if(n<3) return 0; stack s; s.push(0); int water = 0; for(int i=1; iA[s.top()]) { int bottom = A[s.top()]; s.pop(); while(!s.empty() && A[i]>=A[s.top()]) { water += (A[s.top()]-bottom)*(i-s.top()-1); bottom = A[s.top()]; s.pop(); } if(!s.empty()) water += (A[i]-bottom)*(i-s.top()-1); } s.push(i); } return water; } }; ```

Hmin <= A[i]时，Si = 0
Hmin > A[i]时，Si = Hmin - A[i]

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ```class Solution { public: int trap(int A[], int n) { if(n<3) return 0; vector leftHeight(n,0); vector rightHeight(n,0); int water = 0; for(int i=1; i=0; i--) { rightHeight[i] = max(rightHeight[i+1], A[i+1]); int minHeight = min(leftHeight[i], rightHeight[i]); if(minHeight>A[i]) water += (minHeight - A[i]); } return water; } }; ```