Trapping Rain Water, Java

Trapping Rain Water

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;
import java.lang.Math;

//Trapping Rain Water

class Rextester
{  
    public static void main(String args[])
    {
        System.out.println(fastTrap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }

public static int trap(int[] height) {
        int maxLeft = 0,maxRight=0;
        int[] res = new int[height.length];
        for(int i=1;i<height.length-1;i++){
            for(int j = i-1;j>=0;j--){
                maxLeft = Math.max(maxLeft,height[j]);
            }
            for(int j = i+1;j<height.length;j++){
                maxRight = Math.max(maxRight,height[j]);
            }
            res[i]=Math.min(maxLeft,maxRight);
            maxLeft = maxRight = 0;
        }
        int stored = 0;
        for(int i=0;i<height.length;i++){
            if(height[i]>=res[i])
                continue;
            stored=stored+res[i]-height[i];
        }
        return stored;
    }

public static int fastTrap(int[] height) {
        if(height==null)
            return 0;
        int size = height.length;
        int[] res = new int[size];
        int[] leftHeight = new int[size];
        int[] rightHeight = new int[size];
        leftHeight[0] = height[0];
        for(int i=1;i<height.length;i++){
            leftHeight[i] = Math.max(leftHeight[i-1],height[i]);
        }

rightHeight[size-1] = height[size-1];
        for(int i = size-2;i>=0;i--){
            rightHeight[i] = Math.max(rightHeight[i+1],height[i]);
        }
        
        int out = 0;
        for(int i = 1;i<size-1;i++){
            out += Math.min(leftHeight[i],rightHeight[i]) - height[i];
        }
        return out;
    }

}


run \| edit \| history \| help	0