A different O(n) approach - easy to understand and simple code


  • 30
    Q
    class Solution {
    public:
        int trap(int a[], int n) {
            int i, res = 0;
            if(!n) return res;
            vector<int> ltr(n, 0), rtl(n, 0);
            for(i = 1, ltr[0] = a[0]; i < n; i++)
                ltr[i] = max(ltr[i-1], a[i]);
            for(i = n - 2, rtl[n-1] = a[n-1]; i >= 0; i--)
                rtl[i] = max(rtl[i+1], a[i]);
            for(i = 0; i < n; i++)
                res += min(ltr[i], rtl[i]) - a[i];
            return res;
        }
    };
    

    observation:

    scan A both from left to right and right to left, record the largest seen during the scan; then for each position the water level should be the min of the 2 large value.


  • -4
    C

    res += min(ltr[i] - a[I], rtl[i]) - a[i];


  • 1
    N

    the same principle with Java.

        if(A.length==0) return 0;
    
        int[] A1=new int[A.length];
        int[] A2=new int[A.length];
        int max=A[0];
        for(int i =0;i<A.length;i++) {
            if(A[i]>max) max=A[i];
            A1[i]=max;
        }
        max=A[A.length-1];
        for(int i=A.length-1;i>=0;i--){
            if(A[i]>max) max=A[i];
            A2[i]=max;
        }
        int sum=0;
        for(int i=0;i<A.length;i++){
         sum=sum+Math.min(A1[i],A2[i])-A[i];
        }
        return sum;
    }
    

  • 0
    C

    truly easy to understand


  • 1
    R

    @qddpx Amazing solution, you just made my day with this solution. Thank you :)


  • 0
    L
    This post is deleted!

Log in to reply
 

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