前言

大家好，今天学习用贪心思想解决摆动序列问题，共三题，分享自己的思路，请大家多多支持

算法思想

大家可以先看看这道我们后面会讲的题看看怎么个事，. - 力扣（LeetCode）

由此题题解说明算法原理，我们可以吧摆动序列的数据放在折线图里，它的大致走向如下

每根线上都可以看作有一个或多个点，这个时候可以想到最大摆动长度就是折线弯折次数（水平的线不计入）自然会想到统计折线的极大值和极小值个数来确定直线，不过对于本题，时候在直线走完后，还会出现两种情况一是直线出来往上走，这个时候正常统计极大和极小值数

红线代表实际的摆动，还有就是往下走，这个时候折线数还是4次

可以知道两种情况都是可以忽略平线的

这类题的贪心就体现在我们在找折线时，总是往后找到折线向上（或向下）能到达的最大高度，这体现了贪心的思想，下面我们具体题目具体分析

1.摆动序列

ok，那么接着上面的题继续往下讲代码实现，我们可以用两个变量实现这题，我们需要一个变量总是记录数组中每一个数据与上一个数据的差值，另一个记录上一个波峰或波谷出现的位置差值，对于平线的情况，可以看出它差值是0，不会让折线数增加，跳过即可，线最后返回值加上结尾的折数

代码

class Solution {public int wiggleMaxLength(int[] nums) {int  ret=0;int left=0;for(int i=0;i<nums.length-1;i++){int right=nums[i+1]-nums[i];if(right==0){continue;}if(right*left<=0){ret++;left=right;}}return ret+1;}
}

2.最长连续递增序列

. - 力扣（LeetCode）

“连续”把这道题难度降低了许多，结合摆动序列思想，暴力+一点贪心就可以很快解决这题

class Solution {public int findLengthOfLCIS(int[] nums) {  int slow=0;int fast=0; int count=0;while(fast<nums.length){int p=fast+1;while(p<nums.length&&nums[p]>nums[p-1]){p++;}count=Math.max(count,fast-slow);slow=fast;}return count;}
}

贪心就体现在我们每次更新slow时不用++而是直接更新到fast停止递增的位置

3.递增的三元子序列

. - 力扣（LeetCode）

思路是类似的，因为是三元所以给了两个a，b，来统计递增个数是否有三个

class Solution {public boolean increasingTriplet(int[] nums) {int a=nums[0];int b=Integer.MAX_VALUE;for(int i=0;i<nums.length;i++){if(nums[i]>b){return true;}else if(nums[i]>a){b=nums[i];   }else{a=nums[i];   }}return false;}
}

好啦，本期博客就到这里，谢谢大家