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