力扣376-摆动序列（java详细题解）

题目链接：https://leetcode.cn/problems/wiggle-subsequence/

前情提要：

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法：局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优，并且没有反例来反驳的话就可以用贪心来试试。

题目思路：

大家首先看到本题，可能会有点懵，什么是摆动序列，其实就是某一个数组里面的所有数它与前一个数的差（prediff）和它后一个数与它的差（curdiff）符号不同，则认为这个数组为摆动序列。

所以我们要做的就是将数组改为这样的一个序列。但其实我们可以不用改数组本身，因为该题要求输出一个结果，我们只要判断该数符合上述规律，如果不符合直接跳过不计数，反之则计数。

那我们怎么利用贪心来做呢？

其实本题的局部最优就是单调坡（上坡或者下坡）上去除多余的节点只保留起始和结束的节点，使其产生峰值和谷值。

全局最优：使整个序列都只存在峰值和谷值。

但本题只思考这些核心思路还不够。

还有三个问题需要考虑。

1.如果上下坡中有平坡怎么处理。

2.首尾俩值如何处理。

3.单调坡中出现平坡怎么处理。

情况一：上下坡中有平坡

如果有平坡，我们可以有俩种处理方式，第一种是留下第一个相等的数值，其余的都删掉，第二种是留下最后一个数值，其余的都删掉。

如图我们采用第二种方式，将前面三个相等的数值删掉，留下最后一个相等的。那么这种怎么用代码表示？

首先我们只拿最后一个2来分析，他的prediff=0,而他的curdiff可以大于0也可以小与0。

然后结合核心思路，只要prediff>=0 && curdiff <0 || predisff <= 0 && curdiff > 0。

就解决第一个情况。

情况二：首尾俩值如何处理。

因为核心思路是有要有三个值，才能产生一个摆动序列。

可是如果只有俩值呢，怎么办?

有俩种处理方式，第一种直接写死，当该数组只有俩值时，写一个处理逻辑。

第二种方式则需要一点代码技巧，我们在第一个值前虚拟加上一个平坡。

如图，如果加上平坡，那么就符合情况一所说，prediff=0，curdiff>0 或者 curdiff<0。

那么第一个值就能够计数，最后一个值我们可以直接初始化计数器为1。

这样首尾俩值就都处理好了。

情况三：单调坡度有平坡

如图我们还会出现这样的情况，如果出现这样的情况，prediff的更新方式就显得尤为重要。

prediff实时更新就是当符合核心思路遍历下一个数值时，prediff就可以直接赋值为curdiff。

如果prediff实时更新的话，当遍历到平坡最后一个2时，因为符合情况1，那么就会造成误判，这个2也会加上。

但这只是单调坡上的平坡，这个2并不能算上。

那么我们怎么解决。

我们可以不用实时更新prediff，只有当出现坡度变化时，即一个数满足核心思路时，则更新prediff就能解决。

最终代码：

class Solution {
    public int wiggleMaxLength(int[] nums) {
        //处理尾数 将result赋值为1
        int result = 1;
        //首部虚拟加上一个平坡 我们只用将prediff赋值为0即可。
        int prediff = 0;
        int curdiff = 0;
        //遍历每一个数值
        for(int i = 0;i < nums.length - 1;i ++){
            //curdiff需要实时更新
            curdiff = nums[i + 1] - nums[i];
            //如果我们实时更新的话 就会导致平坡时候误判。
            //所以我们在这个进行判断 当出现坡度变化才更新prediff。
            if(prediff >= 0 && curdiff < 0 || prediff <= 0 && curdiff > 0){
                result ++;
                prediff = curdiff;
            }
        }
        return result;
    }
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！