Share my solution. It is easy to understand.


  • 0
    S

    At first, find the peak point of the array. Divide the array into left array and right array .

    For the left side array, since the peak point is in the end, so any point less then the current highest point will be trapped. Update the current highest point iteratively.

    For the right side array, reverse the array, iterate as the left side array.

    Add the two side trapped water.

     public int trap(int[] A) {
        if(A.length<=2) return 0;
        int peakposition=0;
        int peakheight=A[0];
        for(int i=1;i<A.length;i++){
            if(A[i]>peakheight){
                peakheight=A[i];
                peakposition=i;
            }
        }
        int left=trap(A,0,peakposition);
        for(int i=0;i<A.length/2;i++){
            int tmp=A[i];
            A[i]=A[A.length-1-i];
            A[A.length-1-i]=tmp;
        }
        int right=trap(A,0,A.length-1-peakposition);
        return left+right;
     }   
       
     public int trap(int[] A, int start, int end){   
        int water=0;
        int peak=A[start];
        for(int i=start+1;i<=end;i++){
            if(A[i]>=peak){
               peak=A[i];
            }else{
                water+=(peak-A[i]);
            }
        }
        return water;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.