Trapping Rain Water

来源：Leetcode

原帖：https://oj.leetcode.com/problems/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 result after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

代码：
1] space complexity

 class Solution {  
 public:   
   //O(1)找到最大值和index  
   int trapWater(int A[], int n) {  
     int max_val = 0, max_ind = 0;  
     for (int i = 0; i < n; i++) {  
       if (A[i] > max_val) {  
         max_val = A[i];  
         max_ind = i;  
       }  
     }  
     int result = 0, start = 0;  
     for (int i = start + 1; i < max_ind; i++) {  
       if (A[i] < A[start]) {  
         result += A[start] - A[i];  
       } else {  
         start = i;      
       }   
     }  
     start = n - 1; //update start  
     for (int i = start - 1; i > max_ind; i--) {  
       if (A[i] < A[start]) {  
         result += A[start] - A[i];  
       } else {  
         start = i;  
       }  
     }  
     return result;  
   }  
 };  

2] space complexity

 class Solution {  
 public:  
   // 改编版本的dp解法 转自http://www.meetqun.com/forum.php?mod=viewthread&tid=425  
   // 刷lc的同学这个题肯定不陌生， 一个常见的的 O（n）的做法是定义两个数组 left 和right  
   // left = [0 , i ]区间最大高度; right = [ i , len-1] 区间最大高度  
   // left 和 right 中较小的那个减去A 便是i位置储水量。   
   // 面试中见到lc 原题并不奇怪，而面试官在原题基础上给你一个此题的follow up也并不新鲜，   
   // 这个题的一个follow up是若某一个bar的高度是0， 代表这个bar漏水， 不能存水， 那你的代码该如何改动去计算储水量？  
   // 面试官只是想吓唬你，看你应变能力，根本就是同一个题。 在计算left 和right 时，判断一下 A是否为0， 若为0， 也为0 便是....  
   int trapWater(int A[], int n) {  
     if (n == 0) return 0;  
     vector<int> left(n);  
     vector<int> right(n);  
     left[0] = A[0];  
     for (int i = 1; i < n; ++i) {  
       left[i] = max(left[i - 1], A[i]);  
     }  
     int res = 0;  
     right[n-1] = A[n-1];  
     for (int i = n - 2; i >= 0; i--) {  
       right[i] = max(right[i+1], A[i]);  
       res += min(right[i], left[i]) - A[i];  
     }  
     return res;  
   }    
 };