本文主要是介绍「贪心算法」摆动序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
力扣原题链接，点击跳转。
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。简单来说，摆动序列的特点是：后一个数交替地比前一个数大或者小。给你一个数组，请找出最长的子数组（保持元素的相对顺序），使得它是一个摆动序列，求这个子数组的长度。
这个问题可以用贪心算法解决。我们把第一个数和最后一个数，再加上所有的极值点（包括极大值点和极小值点）作为摆动序列，这个子数组一定是满足条件的最长子数组，感兴趣的读者可以试着证明这一点。这样，问题就转换为：如何求一个数组极值点的个数？
我们如何判断nums[i]是不是极值呢？一个简单的想法是，如果(nums[i]-nums[i-1])×(nums[i+1]-nums[i])<0，那么nums[i]就是极值。如果这么判断的话，会漏掉一些点。比如，一个序列是1、2、2、2、1，此时2是极大值，但是由于有连续多个相同的值，不能按照前面的方式判断。我们可以换个思路，假设我们把多余的2删掉，把序列变为1、2、1，这样就很好判断了。如何做到这一点呢？我们可以用left保存nums[i]-nums[i-1]的值，如果遇到nums[i+1]=nums[i]的情况，就跳过这个数；如果这个数没有被跳过，再判断左右两边的差是否异号。我在代码中写的是left×right≤0，是为了把第一个数考虑在内。由于还要考虑最后一个数，所以最终结果是cnt+1。
class Solution
{
public:int wiggleMaxLength(vector<int>& nums){int left = 0, cnt = 0, n = nums.size();for (int i = 0; i < n - 1; i++){int right = nums[i + 1] - nums[i];// 不考虑相同的数if (right == 0)continue;// 异号，是极值点if (left * right <= 0)cnt++;left = right;}return cnt + 1;}
};这篇关于「贪心算法」摆动序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
