## Wednesday, January 9, 2013

### [LeetCode] 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.
For example,
Given `[0,1,0,2,1,0,1,3,2,1,2,1]`, return `6`.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Thanks Marcos for contributing this image!
» Solve this problem

[解题思路]

1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
2. 从右往左扫描一遍，对于每一个坐标，求最大右值。
3. 再扫描一遍，求取容积并加和。
#2和#3可以合并成一个循环，

H[i] =  min(  Max( Array[j] ) ,  Max( Array[k]) ) – Array[i]   where  j<i and k>i

[Code]
``````1:    int trap(int A[], int n) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      if(n<2) return 0;
5:      int *maxL = new int[n], *maxR=new int[n];
6:      int max = A[0];
7:      maxL[0] =0;
8:      for(int i =1; i<n-1; i++)
9:      {
10:        maxL[i] =max;
11:        if(max < A[i])
12:          max = A[i];
13:      }
14:      max=A[n-1];
15:      maxR[n-1]=0;
16:      int ctrap,ttrap=0;
17:      for(int i = n-2; i>0; i--)
18:      {
19:        maxR[i] = max;
20:        ctrap = min(maxL[i], maxR[i]) -A[i];
21:        if(ctrap>0)
22:          ttrap+=ctrap;
23:        if(max<A[i])
24:          max = A[i];
25:      }
26:      delete maxL, maxR;
27:      return ttrap;
28:    }
``````