「贪心算法」摆动序列

力扣原题链接，点击跳转。

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。简单来说，摆动序列的特点是：后一个数交替地比前一个数大或者小。给你一个数组，请找出最长的子数组（保持元素的相对顺序），使得它是一个摆动序列，求这个子数组的长度。

这个问题可以用贪心算法解决。我们把第一个数和最后一个数，再加上所有的极值点（包括极大值点和极小值点）作为摆动序列，这个子数组一定是满足条件的最长子数组，感兴趣的读者可以试着证明这一点。这样，问题就转换为：如何求一个数组极值点的个数？

我们如何判断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;
    }
};