Java 2ms O(n) Solution. Easy to understand with simple explanation.


  • 0
    H
    public class Solution {
        public int trap(int[] height) {
            //no water would be contained.
            if(height.length<3) return 0;
            //use two pointers, i from the start, j from the end. 
            int i = 0, j = height.length-1, sum = 0;
            while(i<=height.length-1&&height[i]<=0) i++;
            while(j>=0 && height[j]<=0) j--;
            while(i<j){
                if(height[i] <= height[j]){
                    //move i to right.
                    int wh = height[i];
                    while(wh >= height[i] && i < j){
                        sum += wh - height[i];
                        i++;
                    }
                }else{
                    //move j to left.
                    int wh = height[j];
                    while(wh >= height[j] && i < j){
                        sum += wh - height[j];
                        j--;
                    }
                }
            }
            return sum;
        }
    }

  • 0
    W

    The two lines codes seem not correct coz the height may be negative.
    while(i<=height.length-1&&height[i]<=0) i++;
    while(j>=0 && height[j]<=0) j--;


  • 0
    H

    not sure what are you talking about. this solution is AC


  • 0
    W

    I think height can be negative such as{0,-2,1,0,-16,10,0}


Log in to reply
 

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