Java solution O(n) simple


  • 1
    R
    public int trap(int[] height) {
        int currentMax = 0;
        int sumResult=0;
        int maxHeightIndex = findHighestInded(height);
        for(int index=0; index<maxHeightIndex; index++){
            if(currentMax<=height[index]){
                currentMax=height[index];
            }   
            sumResult+=(currentMax-height[index]);
        }
        currentMax=0;
        for(int index=height.length-1; index>maxHeightIndex; index--){
            if(currentMax<=height[index]){
                currentMax=height[index];
            }   
            sumResult+=(currentMax-height[index]);
        }
        return sumResult;
    }
    
    private int findHighestInded(int[] height){
        int maxIndex = 0;
        for(int index=0; index<height.length; index++){
            if(height[maxIndex]<height[index]){
                maxIndex=index;
            }
        }
        return maxIndex;
    }

Log in to reply
 

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