leetcode刷题指南之WiggleSubsequence

编程与算法之美出品

作者：东大ACM退役校队

编译：刘凯旋

1.题目分析

1.连续数字之差组成的序列：

[1,7,4,9,2,5]的连续数字差序列为[6,-3,5,-7,3]。

2.摆动序列：

由一系列数字组成，它的连续数字差序列是正负交替序列。

如[1,7,4,9,2,5]就是一个摆动序列，因为它对应的连续数字差序[6,-3,5,-7,3]是一个正负交替序列。

3.规定：

·少于两个数字的序列是摆动序列

·前两个数字之差正负均可

[1,4,7,2,5]和[1,7,4,5,5]不是摆动序列，因为第一个序列的前两个差同正，第二个序列最后一个差为0。

给定一组整数序列，返回满足摆动序列性质的最长子序列长度，要求时间复杂度为O(n)。

举例说明

输入: [1,7,4,9,2,5]输出: 6

整个序列是摆动序列。输入: [1,17,5,10,13,15,10,5,16,8]输出: 7

有多个长度为7的摆动序列，其中一个是[1,17,10,13,10,16,8]。输入: [1,2,3,4,5,6,7,8,9]输出: 2

2.解题思路

摆动序列就像绵延的山脉，有峰顶有谷底：...高 低 高 低...

[1(低),7(高),4(低),9(高),2(低),5(高)]

我们来看不满足条件的序列：

[2(高), 1(低), 4(高), 5(高), 6(高), 3(低), 3(平), 4(高), 8(高), 4(低), 3(低)]

可以看出来，由于序列中出现了平、连续的高或连续的低，导致整个序列不满足摆动序列，只要从完整的序列中去掉平、连续的高或者低，得到的子序列就是摆动序列。

比如子序列[2(高), 1(低), 6(高), 3(低), 3(平), 8(高), 3(低)]就是摆动序列。

这样的到的摆动序列一定是最长的：

1.若原序列中出现连续递增序列（[1,4,5,6]），连续递减序列（[8,4,3]）或者连续相等序列（[3,3]），因为子序列要满足摆动序列的性质，因此连续递增序列和连续递减序列只能留两个数，连续相等序列只能留一个数。

2.连续递增序列留的两个数应该是递增序列的两端（[1, 6]），连续递减序列留的两个数应该是递减序列的两端（[8, 3]）。

之所以要留连续递增序列的两端和连续递减序列的两端是为了避免如下的情况：

1. [2, 1, 4, 5, 6, 5]，连续递增序列[1,4,5,6]，如果留[4,5]，得到的子序列为[2,4,5,5]，不满足摆动序列的性质；

2. [4, 8, 4, 3, 4]，连续递减序列[8,4,3]，如果留[8,4]，得到的子序列为[4,8,4,4]；如果留[4,3]，得到的子序列为[4,4,3,4]，均不满足摆动序列的性质。

有了上面的方法，只需要顺序扫描序列即可。

3.代码示例