贪心算法01 中 LeetCode T376 摆动序列"/>
代码随想录 Day26 贪心算法01 中 LeetCode T376 摆动序列
LeetCode T376 摆动序列
题目链接:376. 摆动序列 - 力扣(LeetCode)
前言
这题我们看到可以删除数组中的元素也可以不删除可能就吓到了,其实是这道题可以用动态规划或者贪心的策略去解决问题,这里我们还是用贪心的解法去解决问题,具体动态规划的思路可以参照网站:代码随想录 (programmercarl)
摆动数列的定义
做这题之前我们得明白什么是摆动序列,举个例子[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;}
}
更多推荐
代码随想录 Day26 贪心算法01 中 LeetCode T376 摆动序列
发布评论