摆动序列（贪心算法）

一、题目解析

1. 题目描述

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在）可正可负；仅有一个元素 / 两个不等元素的序列也视作摆动序列。

给定整数数组nums，返回其中作为摆动序列的最长子序列长度（子序列可删除部分元素，剩余元素保持原顺序）。

2. 核心特征

• 摆动核心：相邻差值必须严格正负交替（不能为 0）；
• 子序列特性：无需连续，只需保持元素原始顺序；
• 边界情况：
  • 数组长度 ≤ 1 → 直接返回长度；
  • 数组长度 = 2 → 两元素相等返回 1，不等返回 2。

3. 贪心算法核心思路

纯贪心的核心逻辑是：统计数组中 “有效摆动点” 的数量，最长摆动序列长度 = 摆动点数量 + 1。

4. 核心定义

• 摆动点：当前元素与前一个元素的差值符号，和前一个差值的符号相反且非 0，则当前元素是一个摆动点；
• 初始状态：数组第一个元素默认是 “起点”，计数为 1；
• 遍历过程：只关注 “差值符号变化”，忽略连续相同符号的差值（包括差值为 0），因为这些元素对最长摆动序列无贡献。

5. 贪心策略本质

我们的目标是找到最长的摆动子序列，因此只需要保留每次差值符号变化的元素，跳过连续同方向 / 相同的元素 —— 这就是贪心的 “最优选择”：每一步都选能形成摆动的元素，最终得到全局最长序列。

二、贪心算法完整实现

class Solution { public int wiggleMaxLength(int[] nums) { // 边界情况1：空数组或单元素数组，直接返回长度 if (nums == null || nums.length <= 1) { return nums.length; } // 边界情况2：两个元素的特殊处理（提前判断避免后续逻辑冗余） if (nums.length == 2) { return nums[0] == nums[1] ? 1 : 2; } int maxLen = 1; // 初始长度：第一个元素 int prevDiff = 0; // 记录前一个有效差值（初始为0，表示还未确定方向） // 从第二个元素开始遍历 for (int i = 1; i < nums.length; i++) { // 计算当前元素与前一个元素的差值 int currDiff = nums[i] - nums[i - 1]; // 核心贪心判断： // 1. 当前差值非0（排除连续相同元素） // 2. 当前差值符号与前一个有效差值符号相反 if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) { maxLen++; // 找到摆动点，长度+1 prevDiff = currDiff; // 更新前一个有效差值为当前差值 } // 差值为0 或 符号与前一个相同 → 跳过，不更新 } return maxLen; } }

三、关键代码解析

1. 边界处理

if (nums == null || nums.length <= 1) { return nums.length; } if (nums.length == 2) { return nums[0] == nums[1] ? 1 : 2; }

• 空数组 / 单元素数组：直接返回长度（本身就是摆动序列）；
• 双元素数组：相等返回 1，不等返回 2（符合题目 “两个不等元素视作摆动序列” 的定义）。

2. 核心贪心逻辑

java

运行

if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) { maxLen++; prevDiff = currDiff; }

• currDiff > 0 && prevDiff <= 0：当前上升，且前一个差值是下降 / 初始状态（0）→ 形成摆动；
• currDiff < 0 && prevDiff >= 0：当前下降，且前一个差值是上升 / 初始状态（0）→ 形成摆动；
• 只有满足上述条件，才计数 + 1，并更新prevDiff为当前有效差值（避免后续重复计数）。

3. 变量说明

表格

四、执行过程演示（示例 2）

输入：nums = [1,17,5,10,13,15,10,5,16,8]

表格

最终结果：7，与示例 2 一致。

五、关键测试用例验证

测试用例 1：nums = [1,7,4,9,2,5]

执行过程：

• 差值依次为 6 (+)、-3 (-)、5 (+)、-7 (-)、3 (+)；
• 每次差值符号都相反，共 5 个摆动点，maxLen = 1+5 = 6（正确）。

测试用例 2：nums = [1,2,3,4,5,6,7,8,9]

执行过程：

• 差值全为正，仅第一次上升触发计数（len=2），后续同方向跳过；
• 最终maxLen = 2（正确）。

测试用例 3：nums = [0,0,0]

执行过程：

• 所有差值为 0，无摆动点，maxLen = 1（正确）。

六、复杂度分析

表格

七、总结

1. 纯贪心算法解决摆动序列问题的核心是统计有效摆动点：只保留差值符号变化的元素，跳过同方向 / 相同元素；
2. 关键判断条件：当前差值非 0，且与前一个有效差值符号相反；
3. 时间复杂度 O (n)、空间复杂度 O (1)，是最优解法之一；
4. 边界处理需注意：空数组、单元素、双元素、全相同元素的场景。

当然这道题也可以用贪心算法加上动规来做，有兴趣的可以去试一试