文章目录
- 方法思路
- 解决代码
- 代码解释
摆动序列问题解析
摆动序列要求相邻元素的差正负交替出现。解决该问题的核心是统计这些交替变化的次数，从而确定最长摆动子序列的长度。
方法思路
贪心策略：
- 初始化：使用两个变量
left和right分别记录前一个差和当前差。初始时，left设为0以处理第一个非零差。 - 遍历数组：计算相邻元素的差
right。若right为0，跳过；否则检查其与前一个差left的方向是否不同。 - 统计摆动次数：每当方向变化时，增加计数，并更新
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;}
};
代码解释
- 初始化：
left和right初始化为0，count记录摆动次数。 - 遍历处理：循环计算每对相邻元素的差，忽略零差。当方向变化时，增加
count并更新left。 - 返回结果：摆动次数加1即为最长子序列长度（初始元素算作第一个节点）。
该算法时间复杂度为O(n)，空间复杂度O(1)，高效且简洁。
