# Trapping Rain Water

# Question:

http://www.lintcode.com/en/problem/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.

# Example

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

# Answer

RunTime : 1272ms

```
class Solution {
public:
/*
* @param heights: a list of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
// write your code here
if (heights.size() < 3)
return 0;
int result = 0;
size_t l, r;
l = 0;
r = heights.size() - 1;
while (l < r) {
while (l < r && heights[l] == 0) l++;
while (l < r && heights[r] == 0) r--;
int min = heights[l] < heights[r] ? heights[l] : heights[r];
for (size_t i = l; i <= r; i++) {
if (heights[i] >= min)
heights[i] -= min;
else {
result += min - heights[i];
heights[i] = 0;
}
}
}
return result;
}
};
```