A solution with O(1) space and one-pass time


  • 1
    X
    class Solution {
    public:
        int trap(int A[], int n) {
            if(n <=2) return 0;
            int water = 0;
            int leftBar = A[0], rightBar=A[n-1];
            int start = 1, end = n-2;
            while(start <= end){
                if(leftBar <  rightBar){
                    water += max(leftBar - A[start], 0);
                    leftBar = max(leftBar, A[start]);
                    start++;
                }
                else{
                    water += max(rightBar - A[end], 0);
                    rightBar = max(rightBar, A[end]);
                    end--;
                }
            }
            return water;
        }
    };

  • 0
    A

    excellent work,can u send me your email adress,i want to make a friend with u as well as asking you more question,my email adress is
    angelorlover@yahoo.com,my name is william,hope for your reply!


Log in to reply
 

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