LeetCode 376 摆动序列 - 贪心解法
https://leetcode.cn/problems/wiggle-subsequence/description/
思路
- 直觉上可以看某个点是不是
V或^，但这种写法很难处理“平坡”。 - 实际上，是否计数取决于 方向是否发生变化。
- 如果前后都是上升（中间即使有平坡），就没有新拐点；如果从上升变为下降（或反过来），就产生一个拐点。
因此，只需要关注“非平坡方向”的变化。统计的是 有效上升/下降区间数量，最后答案是“区间数 + 1”。
代码
这里 pre_direction 只有初始为 0，后续一旦遇到非平坡差值就会更新为正或负。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()<=1) return nums.size();
int res = 0;
int pre_direction =0;
for(int i = 1;i<nums.size();i++){
int direction = nums[i] -nums[i-1];
if(direction!=0){
if(direction>0&&pre_direction<=0) res++;
if(direction<0&&pre_direction>=0) res++;
pre_direction = direction;
}
}
return res+1;
}
};