1.题目要保证最后选取的子序列最长，首先想到的就是贪心算法。只遍历一遍数组，遇到符合规则的就放进结果中，如果不满足就跳过。因为题目中说“可以通过删除一些元素来得到子序列”，本题的摆动序列可以想象成很多的波，当前面的元素呈现递增状态时，波峰处的元素（即递增子序列的最后一个元素）一定是一个极大值，此时删掉该元素前面不满足条件的元素即可，这样就能保证后面的元素更有可能满足要求（后续要求为比该元素小）。波谷也是如此。不过本题只要求得出子序列长度，不要求输出子序列。
2.基于以上思想，写出的完整代码如下：
1. // 判断a减b正负：a>b返回1，a<b返回-1，相等返回0
2. int isPositive(int a, int b){
3. if (a – b > 0){
4. return 1;
5. } else if (a – b < 0){
6. return -1;
7. } else {
8. return 0;
9. }
10. }
11.
12. int wiggleMaxLength(int* nums, int numsSize) {
13. // 数组只有一个元素，摆动序列长度直接为1
14. if (numsSize == 1) return 1;
15.
16. // cur：当前最长摆动子序列长度
17. int cur = 1;
18. // last：上一段差值正负标记，2代表还未记录过有效差值
19. int last = 2;
20.
21. // 从第二个元素开始遍历数组
22. for (int i = 1; i < numsSize; i++){
23. // 当前数字和前一个相等，无差值，直接跳过
24. if (nums[i] == nums[i – 1]) continue;
25. // 还没有记录过有效升降趋势
26. if (last == 2){
27. // 记录当前升降方向
28. last = isPositive(nums[i], nums[i – 1]);
29. // 序列长度+1
30. cur++;
31. continue;
32. }
33.
34. // 当前升降趋势和上一段不同，形成摆动，长度+1
35. if (isPositive(nums[i], nums[i – 1]) != last){
36. cur++;
37. }
38. // 更新上一段的升降标记为当前趋势
39. last = isPositive(nums[i], nums[i – 1]);
40. }
41.
42. return cur;
43. }
该算法时间复杂度为O(n)，空间复杂度为O(1)。
3.该题本质上就是求数组的方向变化次数，更简洁的代码版本如下：
1. int wiggleMaxLength(int* nums, int numsSize) {
2. // 数组仅有一个数字，最长摆动子序列长度为1
3. if (numsSize == 1) return 1;
4.
5. // direction记录上一组相邻数字的差值，INT_MAX代表还未记录有效差值
6. int direction = INT_MAX;
7. // res保存最长摆动子序列长度，初始最少为1
8. int res = 1;
9. // 从第二个元素开始遍历数组
10. for (int i = 1; i < numsSize; i++){
11. // 当前数字与前一位相等，无波动，直接跳过
12. if (nums[i] == nums[i – 1]) continue;
13. // 还没有记录过有效升降差值
14. if (direction == INT_MAX){
15. // 记录当前相邻数字差值作为初始方向
16. direction = nums[i] – nums[i – 1];
17. // 找到第一个波动，序列长度+1
18. res++;
19. }
20.
21. // 上一段上升，当前段下降，出现摆动，长度+1并更新方向
22. if (direction > 0 && nums[i] – nums[i – 1] < 0){
23. res++;
24. direction = nums[i] – nums[i – 1];
25. }
26. // 上一段下降，当前段上升，出现摆动，长度+1并更新方向
27. else if (direction < 0 && nums[i] – nums[i – 1] > 0){
28. res++;
29. direction = nums[i] – nums[i – 1];
30. }
31. // 若和上一段升降方向相同，不做任何操作，不更新长度
32. }
33.
34. return res;
35. }
该算法时间复杂度为O(n)，空间复杂度为O(1)。本质上还是贪心算法。
