题目：
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.
分析：此题出的的确很有意思，我的解法是遍历每一层求雨水数。
比如给定的数组为[0,1,0,2,1,0,1,3,2,1,2,1]，首先分别从数组的两端同时遍历数组，找到不为零的两个端点，分别是第二个位置和第十二个位置；
其次遍历数组，计算出第一层捕获的雨水数，这样第一层能捕获到两个单位；接下来可以递归求解每一层，当遍历完整个数组，算法也就结束了。
note：看似是在用遍历每一层的思想求解，事实上算法的时间复杂度为O（N）。
代码如下：
int slove(int A[],int begin,int end)
{
if(end-begin<=1)return 0;
while(A[begin]==0)begin++;
while(A[end]==0)end--;
int count=0;
if(A[begin]>=A[end]&&(end-begin>1))
{
for(int i=begin+1;i
if(A[i]
count+=A[end]-A[i];
A[i]=0;
}
else
{
A[i]-=A[end];
}
}
A[begin]-=A[end];
A[end]=0;
count+=slove(A,begin,end-1);
}
if(A[begin]
{
for(int i=begin+1;i
if(A[i]
count+=A[begin]-A[i];
A[i]=0;
}
else
{
A[i]-=A[begin];
}
}
A[end]-=A[begin];
A[begin]=0;
count+=slove(A,begin+1,end);
}
return count;
}
int trap(int A[], int n) {
if(n<=1)return 0;
int result=slove(A,0,n-1);
return result;
}