Find maximum, then increasing sequence from left and right up to the maximum


  • 0
    L
    class Solution {
    public:
        int trap(int A[], int n) {
            int max_ind = max_element(A, A+n) - A;
            
            int l = 0, w = 0;
            
            for(int i=1; i<=max_ind; i++){
                if(A[i] < A[l])
                    w += (A[l] - A[i]);
                else 
                    l = i;
            }
            
            l = n - 1;
            for(int i=n-2; i >= max_ind; i--){
                if(A[i] < A[l])
                    w += (A[l] - A[i]);
                else 
                    l = i;
            }
            
            return w;
        }
    };
    
    1. Find the index of the first maximum value.
    2. Look for increasing sequence from left up to the max. Add as much water as you can.
    3. Do the same as step 2 from right to left.

    Sharing this since I thought it would be simpler to understand.


Log in to reply
 

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