网上怎样查询企业资质_合肥网络公司有哪些_优化设计英语_东莞企业网站模板建站

摆动序列问题解析

摆动序列要求相邻元素的差正负交替出现。解决该问题的核心是统计这些交替变化的次数，从而确定最长摆动子序列的长度。

方法思路

贪心策略：

1. 初始化：使用两个变量left和right分别记录前一个差和当前差。初始时，left设为0以处理第一个非零差。
2. 遍历数组：计算相邻元素的差right。若right为0，跳过；否则检查其与前一个差left的方向是否不同。
3. 统计摆动次数：每当方向变化时，增加计数，并更新left为当前差。最终摆动次数加1即为所求长度。

关键点：方向变化的判断通过乘积是否非正来确定，确保每次变化的差都被正确统计。

解决代码

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

代码解释

1. 初始化：left和right初始化为0，count记录摆动次数。
2. 遍历处理：循环计算每对相邻元素的差，忽略零差。当方向变化时，增加count并更新left。
3. 返回结果：摆动次数加1即为最长子序列长度（初始元素算作第一个节点）。

该算法时间复杂度为O(n)，空间复杂度O(1)，高效且简洁。