贪心算法----摆动序列

今日题目：leetcode376

点击跳转题目

观察样例2：

发现最长摆动序列都是极大值和极小值 再加上两个端点，那么我们保证每次都能选择到每个极值点，就能从局部最优推广全局最优了！

但是还有一些细节情况需要注意，就是如果出现连续相同的值，如图：

• 对于上图中左边的两种情况，整体是呈现单调递减的，没有出现极值点，不用记录进摆动序列
• 对于上图中右边的两种情况，是等价于极值点的，只需记录一个进摆动序列即可
• 综上，遇到连续相同的值时，我们只需要考虑相同值中最靠后的位置的那个值，其他的忽略，这样就转化为把相同元素”删除“成只剩一个元素的情况

遍历数组时，我们可以用一个left来记录这个值左边是递增还是递减，然后和这个数的右边判断，单调性不同即可记录该元素

代码：

class Solution {
public:
    
    int wiggleMaxLength(vector<int>& nums) 
    {
        int cnt = 0;
        //记录每个元素左边的单调性，初始为0为了记录第一个值为摆动元素
        int left = 0;
        for(int i = 0; i < nums.size() - 1; i++)
        {
            int right = nums[i+1] - nums[i]; //得出右边的单调性
            if(right == 0) continue;
            //符号相反，表示单调性不同，是极值点
            if(left * right <= 0) cnt++;       
            left = right;//迭代为下一个元素左边的单调性
        }
        return cnt+1; //+1是为了记录原数组最后一个值
    }
};