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;
}
};
