摆动序列_摆动性名词解释

题目

思路

首先理解一下什么是摆动序列，摆动序列就是两两之间的差是正数和负数交替，那么首先来分析一下该题的边界问题：第一个边界就是单个元素也属于摆动序列，第二个边界就是一个摆动序列只有两个元素（意味着他们的差为正数或者负数）
那么我们的思路是什么呢，该题的标签为贪心算法的范畴，那我们如何从贪心算法入手呢？

参考思路一

既然要求最长摆动序列长度，那么我们就按照摆动序列的定义来，相比较上一次的差为正数或者负数，来选择本次符合条件的元素，为此我们可以设置两个变量pre和cur，分别表示上一次和现在的差为正数或者负数（正数我们用1表示，负数我们用-1表示），如果pre和cur不等，说明是符合摆动序列的定义的，那么我们就将该元素加入到摆动序列中，否则就不加，相关代码如下：

class Solution { public: int wiggleMaxLength(vector<int>& nums) { int size = nums.size(); if (size < 2) return size; int pre = 0; int cur; int res = 1; for (int i = 1; i < size; i++) { if (nums[i] == nums[i - 1]) continue; cur = nums[i] > nums[i - 1] ? 1 : -1; res += cur != pre; pre = cur; } return res; } }; 

首先我们把变量pre初始化为0，这样就能解决边界问题，因为对于最初的两个数的差，无论为正数或者负数，都能将之纳入到摆动序列范围内，返回的变量初始值设为1（表示边界）
每次我们都判断此时的差为正数或者负数（保存在cur变量中），然后和pre变量相比较，不相等的就纳入摆动序列范围，同时将pre变量更新为cur的值

参考思路二

这个思路比较巧妙，摆动序列用图像来表示的话，实际上就是一个由波峰和波谷交替构成的图像，那么我们可以设置两个变量up和down分别表示波峰和波谷的数量，在摆动序列中，任意一个波峰的数量等于之前波谷的数量加1，同样任意一个波谷的数量等于之前的波峰的数量加1
那么我们就可以利用上述的性质来求出问题的解，相关代码为：

class Solution { public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); if (n < 2) { return n; } int up = 1; int down = 1; for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) { up = down + 1; } if (nums[i] < nums[i - 1]) { down = up + 1; } } return max(up, down); } } 

我们分别初始化up和down的值为1，表示第一个元素肯定是摆动序列范围内，然后我们再遍历数组，对于一个递增的序列，他们之前的波谷的数量是相同的，同样的，对于一个递减的序列，波峰的数量也是一样的，最后返回波峰和波谷中的最大值

总结

在该题中，我们只需要比较在当前阶段判断当前子问题的状态（这里指的是两个元素之间的差），选择最优解（最优解指的是如果满足则加入序列，不满足就不加入序列），通过每次做出最优的选择，最终得到整体的最优解（因为每次我们都选择加入能构成摆动序列的元素，所以最后整个序列也确定是摆动序列）