当前位置：首页 > article >正文

【贪心算法第四弹——376.摆动序列】

article 2024/11/27 10:04:52

1.题目解析

题目来源

测试用例

2.算法原理

3.实战代码

代码解析

本题还可以使用动态规划的解法来解决，不过动态规划的时间复杂度为O(N^2)，而贪心解法的时间复杂度为O(N)，动态规划方法的博客链接: 动态规划-子序列问题——376.摆动序列

1.题目解析

题目来源

376.摆动序列——力扣

测试用例

2.算法原理

贪心策略：找极值，定首尾

具体实现思路以及特殊情况处理

这里求极值需要使用两个变量来确定每个节点的左右状态，当左右相乘为负数说明此点为极值点，那么左右状态分别是什么呢，这里我们只解释右状态的含义(左状态同理)，右状态就是当前节点右边与相邻节点之差(后减去前)，此时差值大于0说明右边是上升，小于0则是下降，左状态同理，因此当两边状态不同也就是相乘为负数则代表该点为极值点

特殊情况判断：

3.实战代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int left = 0;
        int ret = 0;
        int n = nums.size();
        if(n < 2)
        {
            return n;
        }
        for(int i = 0;i < n - 1;i++)
        {
            int right = nums[i+1] - nums[i];
            if(right == 0)
            {
                continue;
            }
            if(left * right <= 0)
            {
                ret++;
            }
            left = right;
        }
        return ret + 1;
    }
};