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!

用stack做了半天没做出来，结果看到这位仁兄的博客http://blog.unieagle.net/2012/10/31/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Atrapping-rain-water/

恍然大悟。代码分分钟：

 1     int trap(int A[], int n) {
 2         int sum=0,lmax=0,rmax=0;
 3         int* left = (int*)malloc(sizeof(int)*n);
 4         memset(left,0,sizeof(int)*n);
 5         for(int i=0;i<n;i++){
 6             left[i]=lmax;
 7             if(A[i]>lmax) lmax=A[i];
 8         }
 9         for(int j=n-2,rmax=A[n-1];j>=0;j--){
10             int delta = min(left[j],rmax)-A[j];
11             if(delta>0) sum+=delta;
12             if(A[j]>rmax) rmax=A[j];
13         }
14         free(left);
15         return sum;
16     }