Java solution with explaination


  • 0
    J

    Hi my friend,

    Here is my solution and I hope it will help you.
    This question seems hard at the first look, but after thinking for a while, you will find out the the only thing that matters is always the current item "nums[i]".

    if the current one is still in the previous changing direction, it can always be a better value to form a wiggle.
    If the current one is in the other direction, then you will only remember it and update the changing direction.

    for example: 1 2 3 4 5 1
    when see "2", you remember "2" and mark direction as increasing. then "3" is still increasing, so you can forget "2" and just remember "3". then just remember "4", then just "5".
    When you see the last "1", you know the direction is changed to decreasing, and you can forget "5", just remember "1".

    Here is the code, please notice I use Integer.compare() to easy determine the direction.

    public int wiggleMaxLength(int[] nums) 
        {
            if (nums == null || nums.length == 0) return 0;
            
            int current = nums[0];
            int direction = 0; // default value, we handle equal case in another way, so it will never be "0".
            int count = 1;
            for (int i=1; i<nums.length; i++)
            {
                if (nums[i] == current) continue; // equal case.
                if (direction != Integer.compare(current, nums[i]))
                {
                    // if direction changed, wiggle will grow by 1.
                    direction = Integer.compare(current, nums[i]);
                    count++;
                }
                current = nums[i]; // as i said, I always remember the current value.
            }
            return count;
        }
    

Log in to reply
 

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