leetCode 376.摆动序列贪心算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetCode 376.摆动序列贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

>>思路和分析

思路1：贪心思路

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列

试试贪心：局部最优推出全局最优，并举不出反例！！！

实际操作上，可以不用做删除操作，由于题目要求的是最长摆动子序列的长度，所以只需要统计数组的局部峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）这也就是贪心所贪的地方。

（1）如何表示一个波动呢？

curdiff = nums[i+1] - nums[i];
prediff = nums[i] - nums[i-1];

如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计

摆动序列贪心算法,贪心算法,leetCode,leetcode,算法,贪心算法,摆动序列

（2）如果出现平坡又该如何解决呢？我们继续往下看~

平坡有两种：一个是上下中间有平坡，一个是单调中间有平坡

摆动序列贪心算法,贪心算法,leetCode,leetcode,算法,贪心算法,摆动序列

① 情况一：上下坡中有平坡

例如 [1,2,2,2,1]，它的摆动序列长度是3，也就是我们在删除的时候要不删除左面的三个2，要不就删除右面的三个2

摆动序列贪心算法,贪心算法,leetCode,leetcode,算法,贪心算法,摆动序列

在图中，当 i 指向第一个2的时候，prediff > 0 && curdiff = 0，当 i 指向最后一个2的时候，prediff = 0 && curdiff < 0

若采用删除左面三个2的规则，那么当 i 指向第一个2的时候，prediff = 0 && curdiff < 0，也要记录一个峰值。这是由于它是把之前相同的元素都删除留下的峰值

所以这里记录峰值的条件可以允许prediff = 0，也就是：prediff <= 0 && curdiff > 0 或者 prediff >= 0 && curdiff < 0 。也就是说相同数字连续的时候，prediff = 0,curdiff < 0 或者 >0 也就为波谷

② 情况二：数组首尾两端

问题思考(O_O)? 统计峰值时，数组的最左面和最右面如何统计呢？

例子：序列[2,5]，摆动序列为2。

上文提到 prediff = nums[i] - nums[i-1] 和 curdiff = nums[i+1] - nums[i] 的时候，可知至少需要三个数字才能计算。因其靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。而此时序列数组只有两个数字，如何将我们的判断规则结合在一起呢？

不妨假设数组前面还有一个数字，也就是将序列[2,5]，假设为[2,2,5]，此时这就有了坡度prediff = 0。而这正是上文讨论的情况一，那么也可以记为一个波谷

摆动序列贪心算法,贪心算法,leetCode,leetcode,算法,贪心算法,摆动序列

针对以上情况，result 初始为 1 （默认最右面有一个峰值），此时curdiff > 0 && prediff <= 0 ，那么result++ （计算了左面的峰值），最后得到的 result 就是 2（峰值个数是2，也就是摆动序列长度为2）

所以说可以初始化 prediff = 0,result = 1

③ 情况三：单调坡中有平坡

摆动序列贪心算法,贪心算法,leetCode,leetcode,算法,贪心算法,摆动序列

上图中，可以计算最长的摆动的序列的长度为3，但其实结果应该为2。这是因为上图是不加限制的实时更新prediff，这会导致单调中的平坡被算为峰值。

摆动序列贪心算法,贪心算法,leetCode,leetcode,算法,贪心算法,摆动序列

什么时候该更新prediff呢？只需要在这个坡度摆动变化的时候，更新prediff就行，这样prediff在单调区间有平坡的时候，就不会发生变化，也就不会产生误判！

>>分析上面两张图和问题思考(O_O)?

问题出在prediff 是一直跟着curdiff去更新的，其实prediff是没有必要去跟着curdiff去实时变换的，prediff只需要统计坡度有变化的时候，记录一下这个坡度的原始方向。例如说在第一个 2 的位置，prediff是有变化的，因为在 1 那里默认它有个平坡（情况二），然后在有变化的时候，prediff就记录一下这个坡度的初始值，也就是初始的坡度的方向。后面这个prediff就没有必要去变化了。那它什么时候去变化呢？除非这个坡度的方向改变了，也就是说遇到了一个摆动，之后prediff就可以记录一下下一个坡的坡度方向。那这样，prediff只记录这个坡度变化的时候的初始坡度，这样有什么好处呢？就是遇到平坡的时候prediff是不会去改变的。那这样在这个代码逻辑中，也不会去记录第三个2认为出现了一个摆动（因为第三个2那里如果prediff是一直实时更新的，就出现prediff = 0,curdiff > 0，这种情况其实是情况二的场景，会被认为是一个摆动）。所以，解决方案就是：prediff只记录当摆动出现的时候，下一个坡的初始坡度，然后prediff就不用去改变了，直到遇到下一个摆动的时候，又改变坡的方向了，prediff可以再去改变，这样就可以绕过这种平坡的情况。体现在代码里应该怎么改呢？可以将prediff=curdiff放在if里面。当出现摆动的时候，再去更新prediff，这样就可以绕过平坡的这种情况。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        int prediff = 0; // 前一对差值
        int curdiff = 0; // 当前一对差值
        int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
        for(int i=0;i<nums.size()-1;i++) {
            curdiff = nums[i+1] - nums[i];
            // prediff=curdiff放在if里面，为的是处理单调有平坡的这种情况
            if((prediff >=0 && curdiff<0) || (prediff <=0 && curdiff>0)) { // 出现峰值
                result++;
                prediff = curdiff; // 注意这里，只在摆动变化的时候更新prediff
            }
        }
        return result;
    }
};