Super Short Java O(n) Time, O(1) Space Solution with Detailed Explanation


  • 0
    A
        // We keep two variables. One variable holds the up count, and
        // the other holds the down count. If our current number is greater 
        // than the previous number, then we have wiggled up. This means 
        // we update up to be 1 + down. If our current number is less than
        // the previous number, then we have wiggled down. This means 
        // we update down to be 1 + up. If our current number equals 
        // the previous number, then we don't do any updates. 
    
       // NOTICE how we don't update "down" when we update "up", 
       // and vice versa. This ensures we don't double count. If we get
       // several wiggle ups in a row, we only get 1 + (the current value 
       // of down). This value for down will never update until we have
       // another wiggle down, so if we had several wiggle ups without
       // any wiggle downs, then up will stay the same, which is what 
       // we want since we didn't add any more wiggles to our 
       // subsequence. 
    
       // Example: [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
       // initialize down and up to 1, since at the very 
       // least we have 1. We ignore the first item since
       // there is clearly no wiggle until we get to at least
       // two items to compare. 
    
       // We start at 17. We have a wiggle up since 17 - 1 > 0.
       // up = down + 1 = 2
       // Now 5 - 17 < 0, so we have a wiggle down
       // down = up + 1 = 3 
       // Now 10 - 5 > 0, so up = down + 1 = 4
       // Now 13 - 10 > 0, so up = down + 1 = 4
       // Now 15 - 13 > 0, so up = down + 1 = 4
       // Notice how a sequence of wiggle ups 
       // without wiggle downs 
       // did not make up larger than it should be! 
    
       // Now 10 - 15 < 0, so down = up + 1 = 5
       // Now 5 - 19 < 0, so down = up + 1 = 5
       // Now 16 - 5 > 0, so up = down + 1 = 6
       // Now 8 - 16 < 0, so down = up + 1 = 7
    
        public int wiggleMaxLength(int[] nums) {
            if(nums.length < 2) return nums.length;
            int up = 1;
            int down = 1;
            for(int i = 1; i < nums.length; i++) {
                if(nums[i] > nums[i - 1]) up = down + 1;
                else if(nums[i] < nums[i - 1]) down = up + 1;
            }
            return Math.max(up, down);
        }
    

Log in to reply
 

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