376. 摆动序列（Wiggle Subsequence）

频次 ★★★ · 难度 🟡 · 高频：字节/美团

题目

如果连续数字之间的差值严格正负交替，则称为摆动序列。第一个差值（如果存在）可以是正或负。只有一个元素或两个不等元素的序列也是摆动序列。返回最长摆动子序列的长度。

示例：

输入: nums = [1,7,4,9,2,5]
输出: 6 （整个序列就是摆动序列：1,7,4,9,2,5）

输入: nums = [1,17,5,10,13,15,10,5,16,8]
输出: 7 （[1,17,10,13,10,16,8]）

输入: nums = [1,2,3,4,5,6,7,8,9]
输出: 2 （[1,2] 或任意两个不等元素）

思路

贪心（统计极值点数量）：摆动序列等价于序列中的”峰”和”谷”交替出现。我们只需要统计有多少个极值点（峰或谷），加上首尾元素即可。

实现：维护 prediff（前一对差值）和 curdiff（当前差值），当 prediff 和 curdiff 异号时，说明遇到了一个极值点，计数加一。

平坡处理：遇到连续相等元素时跳过（curdiff == 0 不更新 prediff），只在真正出现摆动时才更新 prediff。

代码

public int wiggleMaxLength(int[] nums) {
    if (nums.length <= 1) return nums.length;
    int prediff = 0;    // 前一对差值
    int curdiff = 0;    // 当前差值
    int count = 1;      // 最右边元素算一个峰值
    for (int i = 0; i < nums.length - 1; i++) {
        curdiff = nums[i + 1] - nums[i];
        // 出现摆动（异号）；prediff 可以为 0 处理开头
        if ((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) {
            count++;
            prediff = curdiff;   // 只在摆动时更新 prediff，跳过平坡
        }
    }
    return count;
}

复杂度

• 时间：O(n) —— 一次遍历
• 空间：O(1)

边界条件

• 长度为 1：返回 1
• 全相等（如 [1,1,1,1]）：返回 1（只有一个元素算摆动序列）
• 单调递增/递减：返回 2（首尾两个元素）
• 开头有平坡（如 [1,1,2]）：prediff 初始为 0，curdiff 为正时触发计数，正确处理

变式

• 300. 最长递增子序列：动态规划版，求最长递增子序列长度
• 324. 摆动排序 II：构造摆动序列，而非求长度

易错点

• prediff 更新时机：只在摆动发生时更新，平坡（curdiff == 0）时不更新。否则会把平坡误判为摆动
• prediff 初始为 0：处理首元素，prediff = 0 时遇到任何非零 curdiff 都算摆动
• count 初始为 1：最右边元素天然算一个峰值，因为我们需要的是峰/谷数量，等价于摆动序列长度

面试追问

• 为什么贪心是正确的？ 摆动序列等价于找所有极值点，因为中间的非极值点可以删除而不影响摆动性质。贪心”遇到极值就计数”等价于选所有极值点
• 能用 DP 做吗？ 可以，up[i] 和 down[i] 分别表示以 i 结尾且最后是上升/下降的最长摆动子序列长度，但贪心 O(n)/O(1) 更优

关联题

• 同套路：300. 最长递增子序列 —— DP 版最长子序列
• 进阶：324. 摆动排序 II —— 构造而非求长度
• 知识点：序列贪心之”极值点”模板见贪心