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

本文主要是介绍贪心算法----摆动序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今日题目：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是为了记录原数组最后一个值}
};

这篇关于贪心算法----摆动序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---