Straightforward O(N) solution


  • 0
    H

    Scan from left to right, store the direction and current value. If direction changes, update direction, length and current value; if direction does not change, update current value;

    public int wiggleMaxLength(int[] nums) {

        // edge cases
        if (nums == null || nums.length == 0)
            return 0;
        else if (nums.length == 1)
            return 1;
        else if (nums.length == 2) {
            return nums[1] == nums[0]? 1: 2;
        }
      
            
        int cur;
        boolean up;
        int len = 0;
        
        int start = 1;
        while (nums[start] == nums[start-1]) {
            start++;
            if (start >= nums.length - 1)   // all same value in this array
                return 1;
        }
        
        // start is the first index that satisfies nums[start] != nums[start -1]
        up = nums[start] > nums[start-1];
        len = 2;
        cur = nums[start];
            
        for (int i = start+1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) { // equal case
                continue;
            }
            else if (up && (nums[i]  < nums[i-1]) || 
                 !up && (nums[i] > nums[i-1])) {
                     // a valid wigly
                     up = !up;
                     len ++;
                     cur = nums[i];
            } else {    // following the same trend, update cur and continue
                cur = nums[i];
            }
            
        }
        
        return len;
        
    }

  • 0
    Q

    I started with similar code, but found that

    1. cur is not necessary
    2. in the last for loop, you don't need 3 cases; simply > and <

  • 0
    H
    1. Yes, you are correct
    2. The equal case won't hurt, I may leave it there for better understanding

Log in to reply
 

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