LeetCode Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if 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.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:
Input: [1,7,4,9,2,5] Output: 6 The entire sequence is a wiggle sequence. Input: [1,17,5,10,13,15,10,5,16,8] Output: 7 There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8]. Input: [1,2,3,4,5,6,7,8,9] Output: 2Follow up: Can you do it in O(n) time?
一个抖动序列是指第一个数比第二个数小，第二个数比第三个数大，第三个数比第四个数小…或者第一个数比第二个数大，后续类似的交替的大小关系。 现给定一个数组，要求数组中最长的抖动序列的长度。 首先可以用贪心的方法，每次我们选择数据的拐点（局部最大或最小值点）。比如下图中，第一选了A，后续一直是上升的趋势，则选择最大的D能获得更长的抖动序列长度。如果此时选较小的C的话，则下一个只能选H了，这样就漏了E和G。
贪心的代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int ans = 1, i = 0, j = 1;
bool up = false;
while (j < n && nums[j] == nums[i])++j;
if (nums[j] > nums[i])up = true;
else up = false;
while (j < n) {
if (nums[j] > nums[i] && up) {
++ans;
up = false;
while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
}
else if (nums[j] < nums[i] && !up) {
++ans;
up = true;
while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
}
i = j++;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以用动态规划的方法，假设up[i]表示第i个元素处于抖动序列的最后一个位置，且是上升的趋势时，前[0,i]的抖动子序列的最大长度。类似的，down[i]表示第i个元素处于抖动序列的最后一个位置，且是下降趋势时，前[0,i]的抖动子序列的最大长度。
则对于第i个元素，可以枚举所有i前面的元素j跳到i，如果nums[i]>nums[j]，则i处于抖动序列的上升末尾，则从j到i构成的抖动序列中，j是处于下降趋势的，所以有up[i]=max(up[i],down[j]+1)。类似的，如果nums[i]<nums[j]，则有down[i]=max(down[i],up[j]+1)。最后返回1+max(up[n-1],down[n-1])。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
}
}
return 1 + max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时6MS。
可以对上述代码优化。j无需枚举所有i前面的元素，而是i直接根据和前一个元素i-1的大小关系进行更新。如果nums[i]>nums[i-1]，则i处于上升末端，所以i-1必须处于下降末端，有up[i]=down[i-1]+1，down[i]不变，即down[i]=down[i-1]。如果nums[i]<nums[i-1]，则i处于下降末端，所以i-1必须处于上升末端，有down[i]=up[i-1]+1，up[i]不变，即up[i]=up[i-1]。如果nums[i]==nums[i-1]，则up[i]和down[i]都不变，分别等于up[i-1]和down[i-1]。
为什么这里可以不用枚举所有i前面的元素了呢，因为上述三种情况中，只更新了该更新的，不能更新的情况都等于前一个元素的结果了，比如第一种情况更新了up[i]，则down[i]保持了down[i-1]的值，所以后续如果要用到down[i-1]的值，也可以直接用down[i]的值了。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
up[0] = down[0] = 1;
for (int i = 1; i < n; ++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 max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以对上述代码进行空间的优化，因为up[i]和down[i]都只用到了前一个结果up[i-1]和down[i-1]，所以只需保留前一个结果就行，不需要两个数组。代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i – 1]) {
up = down + 1;
}
else if (nums[i] < nums[i – 1]) {
down = up + 1;
}
}
return max(up, down);
}
};
[/cpp]
本代码提交AC，用时0MS，是效率最好的一种解法了。
参考：https://leetcode.com/articles/wiggle-subsequence/，完整介绍了所有方法。]]>