LeetCode376. 摆动序列

题目

分析

摘自Carl大佬总结

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）但题目只要求返回i长度，所以并不需要真的删除。最后统计局部峰值即可。

关键是统计峰值也不好统计有一定的技巧。下面的错误代码就是自己在统计峰值时的错误

错误代码（主要思想是去除峰底和峰顶之间坡上的元素）

 1 class Solution {
 2 public:
 3     int wiggleMaxLength(vector<int>& nums) {
 4         int res = nums.size();
 5         //边界处理
 6         if(nums.size() == 0 || nums.size() == 1) return nums.size(); //没有元素
 7         if(nums.size() == 2 && nums[0] == nums[1]) return nums.size()-1; //两个相同元素
 8         if(nums.size() == 3 && nums[0] == nums[1] && nums[1] == nums[2]) return 1;
 9         
10         for(int i = 1;i <nums.size()-1;i++){  //检查从第二个元素到倒数第二个元素
11             if(nums[i] > nums[i-1] && nums[i+1] < nums[i]) {cout<<nums[i]<<" ";continue;}
12             if(nums[i] < nums[i-1] && nums[i+1] > nums[i]) {cout<<nums[i]<<" ";continue;}
13             if(i > 1 && nums[i] == nums[i-1] && nums[i] == nums[i+1]) {cout<<nums[i];continue;}
14             res--;
15         }
16         return res;
17     }
18 };

上面代码主要总差1，是因为连续三个相同值、连续两个相同值出错，总之讨论繁琐。从总个数中删除非极值点不好做。

正确代码

 1 class Solution {
 2 public:
 3     int wiggleMaxLength(vector<int>& nums) {
 4         if(nums.size() <= 1) return nums.size();
 5         int res = 1;//初始为1，默认最右段有峰值
 6         int cur = 0;//当前对的差值
 7         int pre = 0;//上一对的差值,前置0
 8         for(int i = 1;i < nums.size();i++){
 9             cur = nums[i] - nums[i-1];
10             if((cur > 0 && pre <= 0) || (cur < 0 && pre >= 0)){
11                 res++;
12                 pre = cur;
13             }
14         }
15         return res;
16     }
17 };