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.
分析：此題出的的確很有意思，我的解法是遍歷每一層求雨水數。

比如給定的數組為[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<end;i++)
            {
                if(A[i]<A[end])
                {
                    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]<A[end]&&(end-begin>1))
        {
            for(int i=begin+1;i<end;i++)
            {
                if(A[i]<A[begin])
                {
                    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;
    }