1ms Java with some explanation. Is this O(n) time?


  • 0
    J

    My English is poor... Hope you guys can understand. XD.
    Firstly, traverse array of integers from left to right. When we found the number smaller than pointer, we count the difference between those numbers and the first-decrease one. If pointer meets the summit, then break. If this summit is not the last one of array, We should traverse the remaining array from right to left until pointer meets the summit again. Return the count finally.

    public class Solution {
        public static int trap(int[] height) {
            int max = 0;
            int count = 0;
            int left = 0;
            for(int i = 0; i < height.length;i++){
                if(height[i]>max) max = height[i];// to find the maximal number.
            }
            for(;left < height.length-1; left++){
                if(height[left]==max) break;
                if(height[left+1]<height[left]){
                    int temp = left+1;
                    while(temp<height.length&&height[temp]<height[left]){
                        temp++;
                    }// traverse to find those smaller than height[left]
                    for(int j = left;j<temp;j++){
                        count+=height[left]-height[j];
                    }
                    left = temp-1;
                }
            }
            if(left == height.length-1) return count;
    // If summit is not the last one of array, we should traverse the remaining from right.
            for(int right = height.length-1;right>left;right--){
                if(height[right-1]<height[right]){
                    int temp = right - 1;
                    while(temp>=left&&height[temp]<height[right]){
                        temp--;
                    }
                    for(int k = right;k>temp;k--){
                        count+=height[right]-height[k];
                    }
                    right = temp + 1;
                }
            }
            return count;
        }
    }
    

Log in to reply
 

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