Java solution: O(n) space and time


  • 0
    M

    O(n) space and time

    public class Solution {
        public int trap(int[] height) {
            int[] max = new int[height.length];
            if(height==null || height.length==0){
                return 0;
            }
            
            max[height.length-1]=height[height.length-1];
            for(int i=max.length-2; i>=0; i--){
                max[i]=max[i+1]>height[i+1]?max[i+1]:height[i+1];
            }
            int maxsofar=height[0]>max[0]?max[0]:height[0];
            int sum=0;
            for(int i=1; i<height.length; i++){
                if(height[i]>maxsofar || maxsofar>max[i]){
                    maxsofar=height[i]>max[i]?max[i]:height[i];
                    continue;
                }
                if(height[i]<maxsofar && height[i]!=max[i]){
                    sum+=maxsofar-height[i];
                }
            }
            return sum;
        }
    }
    

  • 0
    J

    @Mino-De you use height.length before checking whether it is null which may cause NullPointerException.


  • 0
    M

    @jywangkeep Thanks. That is right. I haven't edited the code so ppl who read know what you are talking about.


Log in to reply
 

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