Rain Water Trap

Given a non-negative integer array representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.

Follow up:
What is the complexity of your solution?

for input:
A=[0,1,0,2,1,0,1,3,2,1,2,1]
N= sizeof(A)

compute Left[] where Left[i]= Max(A[0..i])     Calculate Max bar height from node 0-i
Left=[0,1,1,2,2,2,2,3,3,3,3,3]

compute Right[] where Right[i]= Max(A[i..N])    Calculate Max bar height from node i-n
Right=[3,3,3,3,3,3,3,3,2,2,2,1]

compute D[] where D[i]=Min(Left[i],Right[i])    Calculate Min bar height between bar before Vs after i, coz only this much water could fill
D=[0,1,1,2,2,2,2,3,2,2,2,1]

compute E[] where E[i]=D[i]-A[i]            Subtract the height of bar i from Max water bars could hold before Vs after
E[i]=[0,0,1,0,1,2,1,0,0,1,0,0]

the answer is sum(E[i])
the complexity is O(N)

public class Solution {
    public int trap(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[]left=new int[A.length];
        int[]right=new int[A.length];
        if(A.length==0) return 0;
        int max=0;
        for(int i =0;i<A.length;i++){
            max=Math.max(max,A[i]);
            left[i]=max;
        }
        max=0;
        for(int i =A.length-1;i>=0;i--){
            max=Math.max(max,A[i]);
            right[i]=max;
        }
        max=0;
        for(int i =0;i<A.length;i++)
            max+=Math.min(left[i],right[i])-A[i];
        return max;
    }
}