package Code;

public class Code42 {
    static int water(int[] height){
        int n = height.length;
        int res = 0;
        int[] leftArr = new int[n];
        int[] rightArr = new int[n];
        leftArr[0] = height[0];
        for(int i = 1; i< n; i++){
            leftArr[i] = Math.max(leftArr[i-1], height[i]);
        }
        rightArr[n-1] = height[n-1];
        for(int i = n-2; i>= 0; i--){
            rightArr[i] = Math.max(rightArr[i+1], height[i]);
        }
        for(int i = 0; i< n; i++){
            res += Math.min(leftArr[i], rightArr[i]) - height[i];
        }
        return res;
    }
    static int water1(int[] height){
        int n = height.length;
        int res = 0;
        int l = 0, r = n-1;
        int leftMax = 0, rightMax = 0;
        while(l < r){
            if(height[l] < height[r]){
                if(height[l] > leftMax){
                    leftMax = height[l];
                }else {
                    res += leftMax - height[l];
                }
                l++;
            }else{
                if(height[r] > rightMax){
                    rightMax = height[r];
                }else{
                    res += rightMax - height[r];
                }
                r--;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(water(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println(water1(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }
}