摆动序列（贪心算法）-平芜编程栈

一、题目解析

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. 变量说明

表格

变量	作用
`maxLen`	记录最长摆动序列长度，初始为 1（第一个元素）
`prevDiff`	记录上一个 “有效摆动” 的差值（非 0），初始为 0
`currDiff`	当前元素与前一个元素的差值

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

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

表格

索引 i	nums[i]	currDiff	prevDiff	maxLen	说明
0	1	-	0	1	初始状态
1	17	16（+）	0	2	上升 + 初始状态 → 摆动点，len+1，prevDiff=16
2	5	-12（-）	16（+）	3	下降 + 上升 → 摆动点，len+1，prevDiff=-12
3	10	5（+）	-12（-）	4	上升 + 下降 → 摆动点，len+1，prevDiff=5
4	13	3（+）	5（+）	4	同方向 → 跳过
5	15	2（+）	5（+）	4	同方向 → 跳过
6	10	-5（-）	5（+）	5	下降 + 上升 → 摆动点，len+1，prevDiff=-5
7	5	-5（-）	-5（-）	5	同方向 → 跳过
8	16	11（+）	-5（-）	6	上升 + 下降 → 摆动点，len+1，prevDiff=11
9	8	-8（-）	11（+）	7	下降 + 上升 → 摆动点，len+1，prevDiff=-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（正确）。

六、复杂度分析

表格

维度	复杂度	说明
时间复杂度	O(n)	仅遍历数组一次，n 为数组长度
空间复杂度	O(1)	仅使用`maxLen`、`prevDiff`、`currDiff`三个常量变量，无额外空间