Java Code 19ms


  • 0
    C
    class Solution {
       /*
        Given n non-negative integers representing an elevation map
        where the width of each bar is 1,
        compute how much water it is able to trap after raining.
        For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
         */
        public int trap(int[] height) {
            if (height.length < 3) return 0;
            int currentHeight = 0,
                highestValue = height[0],
                highestPos = 0,
                totalWater = 0;
    
            for (int i = 1; i < height.length; i++){
                currentHeight = height[i];
                if (currentHeight < highestValue){
                    totalWater += highestValue - currentHeight;
                }else{
                    highestPos = i;
                    highestValue = currentHeight;
                }
            }
    
            if (highestPos != height.length - 1){
                totalWater += calculateLastSectionWater(height,highestPos);
            }
            return totalWater;
        }
    
    
        private int calculateLastSectionWater(int[] heights, int pos){
            /*
            If it cannot be closed at last,
            it must because all integers are small than the first one,
            so we just skip that nubmer.
            However, we falsely add each difference into the total,
            so we should calculate the difference and minus them.
             */
            int len = heights.length - 1,
                    highest = heights[len],
                    currentHeight = 0,
                    firstHeight = heights[pos],
                    difference = firstHeight - highest,
                    i = len - 1, total = 0;
    
            while (i > pos){
                currentHeight = heights[i];
                difference += firstHeight - currentHeight;
                if (highest > currentHeight){
                    total += highest - currentHeight;
                }else{
                    highest = currentHeight;
                }
                i--;
            }
    
            return total - difference;
        }
    }
    

Log in to reply
 

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