[贪心法]leetcode376：摆动序列(medium)

贪心法]leetcode376：摆动序列(medium)"/>

[贪心法]leetcode376：摆动序列(medium)

题目：

题解：

• 贪心法， 贪心的正确性：可想成求波峰和波谷的个数，就可得证了。
• 代码实现：主要使用 flag 来表示前面元素的符号，flag 为 -1 表示前面两个元素的差值为负号，那么此时我们只有nums[i]>nums[i-1]找到正号，才能使序列变长。换句话说前面是波谷，我们需要找到转折点，才能到达波峰，贪心法得证。flag 为 1 表示前面两个元素的差值为正号，那么此时我们只有nums[i]<nums[i-1]找到负号，才能使序列变长。换句话说前面是波峰，我们需要找到转折点，才能到达波谷，贪心法得证。

代码如下：

class Solution {
public://题解：贪心算法，贪心算法的正确性需要数学证明，可简单想成求波峰和波谷的个数之和//思路：扫描一遍数组，最长摆动序列一定包含数组第一个和第二个元素，其余元素根据正负号来进行添加来更新子序列长度int wiggleMaxLength(vector<int>& nums) {//flag表示两个元素之间的正负号，1表示正号，-1表示符号，0用来添加第二个元素与第一个元素的符号int count=1,flag=0,n=nums.size();for(int i=1;i<n;++i){if(nums[i]>nums[i-1]&&(flag==0||flag==-1)){count++;flag=1;}if(nums[i]<nums[i-1]&&(flag==0||flag==1)){count++;flag=-1;}}return nums.empty()?0:count;}
};