376. Wiggle Subsequence

Source link: https://leetcode.com/problems/wiggle-subsequence/

Design

[1,17,5,10,13,15,10,5,16,8] → 7 ([1,17,10,13,10,16,8])

up: 1 2 2 4 4 4 4 4 6 6

down: 1 1 3 3 3 3 5 5 5 7

Method I

  1. Initialize two arrays up and down, the array up is for recording the length of the subsequence that wiggles up, and the array down is for recording the length of the subsequence that wiggles down.
  2. Assign the first element of both arrays with 1.
  3. Travel through the array nums, if nums[i] > nums[i -1], means that the previous element must be a down position, then up[i] = down[i - 1] + 1, down[i] keeps the same value before. If nums[i] < nums[i - 1], means that the previous element must be an up position, then down[i] = up[i - 1] + 1, up[i] keeps the same value as before. If nums[i] = nums[i - 1], then both up[i] and down[i] keeps the same value as before.
  4. Return the max value between last values of both up and down.

Method II

This approach only need two pointers up and down to record the lengths of sequences that wiggle up and down, which could effectively reduce the space complexity.

Implementation

Method I

class Solution {
  public int wiggleMaxLength(int[] nums) {
    if (nums.length == 0 || nums == null) return 0;

    int[] up = new int[nums.length];
    int[] down = new int[nums.length];
    up[0] = 1;
    down[0] = 1;

    for (int i = 1; i < nums.length; i++) {
      if (nums[i] > nums[i - 1]) {
        up[i] = down[i - 1] + 1;
        down[i] = down[i - 1];
      } else if (nums[i] < nums[i - 1]) {
        down[i] = up[i - 1] + 1;
        up[i] = up[i - 1];
      } else {
        up[i] = up[i - 1];
        down[i] = down[i - 1];
      }
    }

    return Math.max(up[nums.length - 1], down[nums.length - 1]);
  }
}

Method II

class Solution {
  public int wiggleMaxLength(int[] nums) {
    if (nums.length == 0 || nums == null) return 0;

    int up = 1, 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);
  }
}

Complexity Analysis

Method I

Time: $O(n)$

Space: $O(n)$

Method II

Time: $O(n)$

Space: $O(1)$