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

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️