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 res