摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
- 输入: [1,7,4,9,2,5]
- 输出: 6
- 解释: 整个序列均为摆动序列。
示例 2:
- 输入: [1,17,5,10,13,15,10,5,16,8]
- 输出: 7
- 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
- 输入: [1,2,3,4,5,6,7,8,9]
- 输出: 2
思路
由题目可知，我们需要做的是找出输入数组中出现"波动"的子序列
这个子序列可以不是连续的（如示例2）
根据题目描述，我们可以将"波动"用图画出来（以示例2为例），大概会呈一个折线的样式
如图所示，我们寻找的是一个整数序列中满足"波动"条件的元素组成的一个序列
在结果中其他元素是可以被忽略的
开始找局部和全局最优
局部最优解：删除出现波动的两个元素构成的坡度上的多余的点，那么该坡度会出现两个波动值，即局部峰值，一个波峰一个波谷
全局最优解：整个输入数组有尽可能多的局部峰值
这里的贪心在贪什么？
贪的是让应该构成峰值的地方尽可能的构成峰值
比如5和15，原本可以构成峰值，但是中间隔了很多元素，那我现在把隔着的玩意删了（不一定要真的删，忽略也行），那不就促成5和15的峰值了吗
摆动条件
现在定义两个变量：前差值prediff和当前差值curdiff
对应到图中如上，17这个位置出现了prediff > 0 && curdiff < 0因此构成一个波动
移动到下一个波动位置，prediff = curdiff，然后重新计算curdiff
此时curdiff = 10，满足条件prediff < 0 && curdiff > 0，又构成一个波动
显然实际情况会更复杂，这里还需要将情况进行细分：
- 情况一：上下坡中有平坡
- 情况二：数组首尾两端
- 情况三：单调坡中有平坡
情况一：上下坡中有平坡
例如 [1,2,2,2,1]
这里的摆动序列其实是[1,2,1]，也就是输出结果一个为3
我们要么删掉左边三个2，要么删掉右边三个2，现在统一删左边的
在图中，当i指向第一个2的时候，prediff > 0 && curdiff = 0 ，当 i 指向最后一个2的时候 prediff = 0 && curdiff < 0。
因为删除的是左边的，因此当满足条件prediff = 0 && curdiff < 0时也要记录一次峰值波动
结合前面对于摆动条件的分析，可以得到包含情况一的摆动条件，即：
(prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)
情况二：数组首尾两端
通过上面的分析可以发现，不论是哪种判断，都需要使用至少3个数来进行
如果出现以下情况就有问题了：
2
/
1
这样的情况无法计算prediff和curdiff
但是题目说了：“少于两个元素的序列也是摆动序列”
也就是说，[1,2]实际上算一个摆动序列，且长度为2
为了统一判断逻辑，这里可以给上述情况设置一个初始值（相当于将[1,2]改成[1,1,2]）
2
/
1--1
这样就满足了prediff = 0 && curdiff > 0的条件
在代码实现时，仅需将结果记录变量res的初始值设置为1即可
代码
在代码实现时，按常理来说，每次记录完res之后要更新prediff为curdiff，这样相当于每次都更新prediff，curdiff没变化也更新
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
//定义前差值prediff和当前差值curdiff
int prediff = 0;
int curdiff = 0;
int res = 1;//初始化结果变量，防止只有两个数的情况
for(int i = 0; i < nums.size() - 1; ++i){//遍历数组，计算curdiff
curdiff = nums[i + 1] - nums[i];
if((prediff >= 0 && curdiff < 0)||(prediff <= 0 && curdiff >0)){
res++;
}
prediff = curdiff;//每次都更新
}
return res;
}
};
这回导致问题，因为数组还会出现以下情况
3
/
2-2-2-2
/
1
如果每次都更新prediff，就会出现prediff == curdiff的情况
这会使代码把平坡处也记录为摆动
但实际上这个数组的摆动序列是[1,3]，在这里平坡不能算波动
平坡算一个上坡的过程中的中间节点，所以实际上应该转变成以下形式
3
/
1-1
1是初始化res得到的
所以，正确的代码应该指在满足波动条件时更新prediff
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
//定义前差值prediff和当前差值curdiff
int prediff = 0;
int curdiff = 0;
int res = 1;//初始化结果变量，防止只有两个数的情况
for(int i = 0; i < nums.size() - 1; ++i){//遍历数组，计算curdiff
curdiff = nums[i + 1] - nums[i];
if((prediff >= 0 && curdiff < 0)||(prediff <= 0 && curdiff >0)){//判断波动条件
res++;//记录波动次数，即摆动序列的长度
prediff = curdiff;//每次都更新
}
}
return res;
}
};
