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]であり、まず配列の両端から配列を同時に遍歴し、ゼロではない2つの端点を見つけ、それぞれ2番目の位置と12番目の位置である.
次に配列を遍歴し、第1層が捕獲した雨水数を計算し、第1層が2単位まで捕獲できるようにした.次に各層を再帰的に解くことができ,完全な配列を巡るとアルゴリズムも終了する.
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] 1))         {             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;     }