My java solution. I think it's quit fast.


  • 2
    S
    public class Solution {
        public int trap(int[] A) {
            if(A.length <= 2) return 0;
            int sum = 0;
            int i;
            for(i = 0; i < A.length; i++){
                if(A[i] != 0) break;
            }
            
            int j = i, k = i+1;
            
            while(k != A.length){
                if(A[j] > A[k]) k++;
                else{
                    int t = k-1;
                    while(t != j){
                        sum += (A[j] - A[t]);
                        t--;
                    }
                    j = k;
                    k++;
                }
            }
            k--;
            if(A[k] < A[j]){
                int t = k-1;
                while(k != j){
                    if(A[t] < A[k]){
                        sum += (A[k] - A[t]);
                        t--;
                    }else{
                        k = t;
                        t--;
                    }
                }
            }
            return sum;
        }
    }
    

    The idea is quit simple. Two pointers, one slow, one fast. The slow one stay at where it is, and the fast one scans from the head to the tail, if the number the fast pointer encounters is larger than the slow one, then calculate the water in this range, and assign the slow pointer to the fast pointer and fast pointer move one step. Repeat this procedure until the fast pointer reach the end. If the number at the end smaller than the slow pointer, then we should calculate the remaining water captured in the last range.


Log in to reply
 

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