[贪心算法] 摆动序列
1.解析
这里我们的贪心体现在，这里我们只需要找到每一个拐点位置的数字即可，
证明：
当我们在A点时，我们下一步的选择有四种
- A到D这个线段内的数字（不包括D）
- 选择D点
- D到F的点
- F之后的点
对于A到D来说，他是一直是上升趋势的，选择之后没有增加序列的长度
D到F的点，他可以选，但是我们选择D点之后，还是会继续走到D到F的点上
而F之后就更不用考虑了，因为这样选择序列的长度一定不会是最大的。
判断是否是怪点
我们在要判断的点的左右两边各假设一个值，left和right；
对于left来说
- 等于0表示不知道数字的变化趋势
- 大于0表示这个点之前是上升趋势
- 小于0表示是下降趋势
对于right，判断方式就是right=nums[i+1]-nums[i];
这里需要注意，right==0时，说明这个点之后出现了平面，这里直接忽视即可，继续向后执行；
最后让left=right；即可向后继续判断
2.代码
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
//left，right
//分别统计左边的趋势，和右边的趋势，如果left*right<0就表示此时的这个点是极值点
int n=nums.size();
long long left=0,right=0;
int count=0;
for(int i=0;i<n-1;i++)//这里注意到n-1即可，因为最后一个一定是，而且还防止right那里越界
{
right=nums[i+1]-nums[i];
if(right==0) continue;//说明现在这个点之后出现了平面，不用管
if(left*right<=0)
{
count++;
left=right;
}
}
return count+1;
}
};