376. 摆动序列

376. 摆动序列

描述：

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

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

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

示例 1:

输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2
进阶:
你能否用O(n) 时间复杂度完成此题?

 1 解法1：4 ms    8.7 MB
 2 class Solution {
 3 public:
 4     int wiggleMaxLength(vector<int>& nums) {
 5         /*思路：
 6             1：这些序列，如果是递增的，那么保留最大的一个1,2,3,4..9  ->9
 7             2:这些序列入是递减的 ,9,8,5,2,1,那么保留保留最小的一个
 8             3:返回序列长度
 9         */
10         if(nums.size()<2) return nums.size();//少于两个元素的序列也是摆动序列
11         
12         int cnt=1;
13         int pre=0,cur=0;
14         for(int i=1;i<nums.size();i++){
15             if(nums[i]!=nums[i-1]){//跳过相等的 数
16                 if(nums[i]>nums[i-1])//只要当前 大于 前一个 
17                     cur=1;//状态标记为1
18                 else cur=-1;//否则 状态标记为-1
19                 if(cur!=pre) cnt+=1;//如果 当前的状态 和 前一个状态 不同 序列长度+1
20                 pre=cur;//更新 先前状态 为 现在的状态，现在状态 下个循环更新
21             }
22         }
23         return cnt;
24     }
25 };

 1 解法2：4 ms    8.6 MB
 2 
 3 class Solution {
 4 public:
 5     int wiggleMaxLength(vector<int>& nums) {
 6         /*思路：
 7            1:动态规划 解法
 8            2:bottom 和up  都代表了 当前 的 最长 摆动序列;初始化为1
 9            3:如果 nums[i]>nums[i-1]  那么 前面一个数 处在 低的位置 i-1
10            4： 此刻 bottom表示这个位置的从 头到 这个 低的位置i-1的 最长 摆动序列长度
11            5:满足条件了，那么 bottom+1就是 i位置的 最长 摆动序列
12            6:如果nums[i]<nums[i-1]  那么 前面一个数 处在 低的位置 i-1
13            7:  此刻up 表示这个位置的从 头到 这个 高的位置i-1的 最长 摆动序列长度
14            8:满足条件了，那么 up+1就是 i位置的 最长 摆动序列
15            9：相等的不考虑
16         */
17         if(nums.size()<2) return nums.size();//少于两个元素的序列也是摆动序列
18         int bottom=1,up=1;//动态规划的优化
19         for(int i=1;i<nums.size();i++){
20             if(nums[i]>nums[i-1]) up=bottom+1;
21             else if(nums[i]<nums[i-1]) bottom=up+1;
22         }
23         return max(up,bottom);
24     }
25 };