JAVA O(n) solution, quite simple idea with explanation, everyone can get it


  • 5

    The idea is quite simple, to get the answer, we just need to remove redundant elements from the array of differences. here comes a simple example:
    for test case:
    [1,17,5,10,13,15,10,5,16,8]
    First, we get array of differences, which are 17-1, 5-17, 10-5....
    [16, -12, 5, 3, 2, -5, -5, 11, -8]
    to become a wiggle sequence, we need these differences to be like [+,-,+,-...] or [-,+,-,+...]
    So, what we need to do is removing all the redundant difference.
    [16, -12, 5, 3, 2, -5, -5, 11, -8], That's it!

    So we assume the length of wiggle sequence is equal to the length of input array, and once we meet a redundant difference, (wiggle sequence)--.

    To distinguish redundant difference, we need to bring in one boolean variable : positive, which tell us the last number in differences is positive or negative.

    One last thing, we deal with the "0" situation, we treat "0" as redundant, and do the same thing.

    Here comes the code: (Please let me know if you have better idea or any suggestion, Thx!)

    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) return nums.length;
        
        int count = nums.length;
        Boolean positive = null;
        
        for (int i = 0; i < nums.length-1; i++){
            int temp = nums[i+1] - nums[i];
            if (temp == 0) count--;
            else if (positive == null) positive = temp > 0;
            else if ((temp > 0 && positive) || (temp < 0 && !positive))
                count--;
            else
                positive = !positive;
        }
        return count;
    }
    
    • list item


Log in to reply
 

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