贪心法]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;}
};
更多推荐
[贪心法]leetcode376:摆动序列(medium)
发布评论