[LeetCode 376] 摆动序列

376. 摆动序列

方法0

出自评论区这位大佬，真的tql%%%
思路其实和下面方法4的状态自动机差不多，但代码就是简洁很多。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return n;
        }
        int up = 1;
        int down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            }
            if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return max(up, down);
    }
};

方法1 暴力

LeetCode官方题解有，好麻烦

方法2 动态规划

留坑

方法3 贪心

状态机

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<2){
            return nums.size();
        }
        static const int BEGIN = 0;
        static const int UP = 1;
        static const int DOWN = 2;
        int STATE = BEGIN;
        int max_length=1;
        
        for(int i=1;i<nums.size();i++){
            switch(STATE){
                case BEGIN:
                    if(nums[i-1]<nums[i]){
                        STATE = UP;
                        max_length++;
                    }else if(nums[i-1] > nums[i]){
                        STATE = DOWN;
                        max_length++;
                    }
                    break;
                case UP:
                    if(nums[i-1]>nums[i]){
                        STATE = DOWN;
                        max_length++;
                    }
                    break;
                case DOWN:
                    if(nums[i-1]<nums[i]){
                        STATE =UP;
                        max_length++;
                    }
                    break;
            }
        }
        return max_length;
    }
};