微信小程序怎么做成链接_b2b电子商务网站的盈利模式_云南网络推广seo代理公司_微信小程序开发平台

目录

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

代码解析