My java solution with O(n),which beat 95%


  • 0
    L
    public class Solution {
        public int trap(int[] height) {
            if(height.length<=2){
                return 0;
            }
            int res = 0;
            int left = 0;
            int right = height.length-1;
            while(left<right){
                if(height[left] <= height[right]){
                    if(height[left+1]<height[left]){
                        res += height[left]-height[left+1];
                        height[left+1] = height[left];
                    }
                    left++;
                }else{
                    if(height[right-1]<height[right]){
                        res += height[right]-height[right-1];
                        height[right-1] = height[right];
                    }
                    right--;
                }
            }
            return res;
            
        }
    }

Log in to reply
 

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