leetcode 376 摆动序列

深藏阁楼爱情的钟 2022-09-14 09:48 136阅读 0赞

## 前言 ##

题目：[376. 摆动序列][376.]

参考题解：[摆动序列-代码随想录][-]

--------------------

## 提交代码 ##

这道题目，我没想出来。看了参考题解，才明白。

摆动序列，等价于，序列的拐点。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSnMTIzNOiNiQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

#include <vector>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            // 统计拐点个数(包含两边端点)
            int result = 0;
            int preDiff = 0;
            int curDiff = 0;
            for(int i=0; i<nums.size()-1; i++){
                curDiff = nums[i+1] - nums[i];
                // if(preDiff & curDiff < 0){
                if((preDiff<=0 && curDiff>0) || (preDiff>=0 && curDiff<0)){
                    result++;
                    preDiff = curDiff;
                }
            }
            result++; // 最后一个默认是拐点
            return result;
        }
    
        void subscriptWiggleMaxLength(vector<int>& nums, vector<int>& subscript){
            // 记录拐点下标
            int preDiff = 0;
            int curDiff = 0;
            for(int i=0; i<nums.size()-1; i++){
                curDiff = nums[i+1] - nums[i];
                if((preDiff<=0 && curDiff>0) || (preDiff>=0 && curDiff<0)){
                    subscript.push_back(i);
                    preDiff = curDiff;
                }
            }
            subscript.push_back(nums.size()-1);
        }
    };
    
    int main(void){
        vector<int> nums = {1,17,5,10,13,15,10,5,16,8};
        Solution s;
        int wiggle_max_length = s.wiggleMaxLength(nums);
        vector<int> subscript;
        s.subscriptWiggleMaxLength(nums,subscript);
        
        cout<<"wiggle max length:"<<wiggle_max_length<<endl;
        cout<<"wiggle max length element:";
        for(auto i : subscript){
            cout<<nums[i]<<" ";
        }
        cout<<endl;
    }

[376.]: https://leetcode-cn.com/problems/wiggle-subsequence/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.md
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSnMTIzNOiNiQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/b702712b28004b49910156b9dbd4690f.png