代码随想录 Day26 贪心算法01 中 LeetCode T376 摆动序列

LeetCode T376 摆动序列

题目链接:376. 摆动序列 - 力扣（LeetCode）

前言

这题我们看到可以删除数组中的元素也可以不删除可能就吓到了,其实是这道题可以用动态规划或者贪心的策略去解决问题,这里我们还是用贪心的解法去解决问题,具体动态规划的思路可以参照网站:代码随想录 (programmercarl.com)

摆动数列的定义

做这题之前我们得明白什么是摆动序列,举个例子[2,6,1,9,3]这个数组,呈现一个波动变化的形态,就称为摆动序列

如果序列只有两个元素,这里就认为摆动序列的长度为2,默认有两个摆动

题目思路:

这题我们首先要考虑情况,我列出以下三种情况:

1.首末元素

2.上下有平坡

3.单调有平坡

变量定义

curDiff:记录当前差值        假设目前遍历到的元素为i  ,curDiff = nums[i+1] - nums[i]

preDiff:记录之前的差值                              preDiff = nums[i] - nums[i-1]

count 记录结果,为了满足默认首尾元素的情况,我们默认count从1开始取值

我们只需要遍历一次数组,满足前后diff不同号即可

注意不能写成curDiff>=0这种情况,因为这样就表示从高或者低值到平坡,是不增加波动的

最后每次结束让pre更新为cur就可以了

这是一个错误的思路,我们是只有遇到了坡度变化才会让pre更新

for(int i = 0;i<nums.length-1;i++)
        {
            curDiff = nums[i+1] - nums[i];
            if((curDiff>0 && preDiff<=0 ) || (curDiff<0 && preDiff>=0))
            {
                count++;
                preDiff = curDiff;
            }
        }

代码模板:

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length<=1)
        {
            return nums.length;
        }
        int preDiff = 0;
        int count = 1;
        int curDiff = 0;
        for(int i = 0;i<nums.length-1;i++)
        {
            curDiff = nums[i+1] - nums[i];
            if((curDiff>0 && preDiff<=0 ) || (curDiff<0 && preDiff>=0))
            {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}