题目

Given an integer array nums, return the length of the longest wiggle sequence.

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

  • For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) are alternately positive and negative.
  • In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

  1. Input: nums = [1,7,4,9,2,5]
  2. Output: 6
  3. Explanation: The entire sequence is a wiggle sequence.

Example 2:

  1. Input: nums = [1,17,5,10,13,15,10,5,16,8]
  2. Output: 7
  3. Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:

  1. Input: nums = [1,2,3,4,5,6,7,8,9]
  2. Output: 2

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Follow up: Could you solve this in O(n) time?

题意

在数组中找到一个子序列，使得子序列中每两个元素的差值一正一负。

思路

比较容易想到的是动态规划。dp[i]表示以nums[i]为结尾的满足条件的子序列的长度，且若最后两个元素之间的差值为负数，dp[i]为负数。对于每一个i，遍历j从0 ~ i-1，找到nums[i]能与dp[j]组成的最大长度的子序列。时间复杂度为0376. Wiggle Subsequence (M) - 图1#card=math&code=O%28N%5E2%29)。

0376. Wiggle Subsequence (M) - 图2#card=math&code=O%28N%29)动态规划：维护两个数组up和down，up[i]表示子数组nums[0-i]中能找到的符合条件的子序列的最大长度，且该子序列的最后一个元素大于倒数第二个元素；down[i]表示子数组nums[0-i]中能找到的符合条件的子序列的最大长度，且该子序列的最后一个元素小于倒数第二个元素。遍历数组，如果当前元素大于前一个，说明可以拓展down[i-1]代表的子序列来得到up[i]；如果当前元素小于前一个，说明可以拓展up[i-1]代表的子序列来得到down[i]。为了进一步减小空间复杂度，可以直接用up和down两个整数来代替数组。

代码实现

Java

动态规划 O(N^2)

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         if (nums.length < 2) return nums.length;
  5.         int maxLen = 1;
  6.         int[] dp = new int[nums.length];
  8.         for (int i = 1; i < nums.length; i++) {
  9.             for (int j = 0; j < i; j++) {
  10.                 int diff = nums[i] - nums[j];
  11.                 if (diff * dp[j] < 0 && Math.abs(dp[j]) + 1 > Math.abs(dp[i])) {
  12.                     dp[i] = dp[j] < 0 ? -dp[j] + 1 : -dp[j] - 1;
  13.                 } else if (dp[j] == 0 && diff != 0 && Math.abs(dp[i]) < 2) {
  14.                     dp[i] = diff < 0 ? -2 : 2;
  15.                 }
  16.             }
  17.             maxLen = Math.max(maxLen, Math.abs(dp[i]));
  18.         }
  20.         return maxLen;
  21.     }
  22. }

动态规划 O(N)

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         if (nums.length < 2) return nums.length;
  5.         int up = 1, down = 1;
  7.         for (int i = 1; i < nums.length; i++) {
  8.             if (nums[i] > nums[i - 1]) {
  9.                 up = down + 1;
  10.             } else if (nums[i] < nums[i - 1]) {
  11.                 down = up + 1;
  12.             }
  13.         }
  15.         return Math.max(up, down);
  16.     }
  17. }