LeetCode 376 摆动序列

摘要

LeetCode 376「摆动序列」是一道看起来像动态规划，最后发现其实是贪心的经典题。
很多人第一反应是：

这不就是求一个子序列吗？那肯定要 DP 啊。

但真正推下来你会发现：
这道题的本质并不在“选哪些数”，而在于相邻差值的“趋势变化”。

这类问题在现实中非常常见，比如：

• 股票价格的涨跌节奏分析
• 传感器数据中的抖动检测
• 用户行为曲线的趋势变化判断

这篇文章会从直觉出发，慢慢推到最终的O(n) 贪心解法，并给出一份非常好理解的 Swift 实现。

描述

题目给了一个整数数组nums，我们需要找一个子序列（可以删元素，但顺序不能变），满足：

• 相邻元素的差值
• 必须在正数 / 负数之间严格交替

注意几个容易踩坑的点：

• 第一个差值可以是正，也可以是负
• 差值为0不算摆动
• 只有一个元素，或者两个不相等元素，也算摆动序列

目标不是判断是否是摆动序列，而是：

在所有可能的子序列中，找出最长的摆动序列长度。

题解答案

最终结论先给出来：

我们只关心“上一次是上升还是下降”，遇到趋势变化就可以计数。

整个过程可以在一次遍历中完成，时间复杂度O(n)，空间复杂度O(1)。

题解代码分析

先用直觉理解摆动序列

我们来看一个最经典的例子：

[1, 7, 4, 9, 2, 5]

差值是：

+6, -3, +5, -7, +3

你会发现一件事：

• 只要方向发生了变化
• 这个点就值得被保留下来

反过来，如果一直在同一个方向：

[1, 2, 3, 4, 5]

无论你选多少个，
最多也只能形成一个“上升”差值，所以答案是2。

贪心的关键点

我们只维护两个状态：

• up：当前以上升差值结尾的最长摆动序列长度
• down：当前以下降差值结尾的最长摆动序列长度

当遍历到nums[i]时：

• 如果nums[i] > nums[i-1]

  • 说明出现了上升
  • 可以把之前的down接过来

• 如果nums[i] < nums[i-1]

  • 说明出现了下降
  • 可以把之前的up接过来

• 相等直接忽略，不产生任何贡献

Swift 可运行 Demo 代码

classSolution{funcwiggleMaxLength(_nums:[Int])->Int{ifnums.count<2{returnnums.count}// up 表示以“上升”结尾的最长摆动序列// down 表示以“下降”结尾的最长摆动序列varup=1vardown=1foriin1..<nums.count{ifnums[i]>nums[i-1]{// 出现上升趋势up=down+1}elseifnums[i]<nums[i-1]{// 出现下降趋势down=up+1}// 相等的情况直接跳过}returnmax(up,down)}}

代码逐行拆解

1. 为什么up和down初始值是 1

因为：

• 单个元素本身就是摆动序列
• 不需要任何差值

2. 为什么可以直接覆盖up/down

这是这道题最“反直觉”的地方。

原因在于：

• 我们只关心“最长”
• 一旦出现新的趋势变化
• 更短的历史路径已经没有任何价值了

这就是贪心成立的根本原因。

3. 为什么可以忽略相等的情况

因为：

差值 = 0

既不是正数，也不是负数，
无法构成摆动的一部分，跳过即可。

示例测试及结果

letsolution=Solution()print(solution.wiggleMaxLength([1,7,4,9,2,5]))// 6print(solution.wiggleMaxLength([1,17,5,10,13,15,10,5,16,8]))// 7print(solution.wiggleMaxLength([1,2,3,4,5,6,7,8,9]))// 2

输出结果：

6 7 2

与题目示例完全一致。

时间复杂度

只遍历一次数组：

O(n)

这是题目进阶要求的最优解。

空间复杂度

只使用了常量级变量：

O(1)

非常适合在性能敏感场景中使用。

总结

LeetCode 376 是一道非常典型的“从 DP 转向贪心”的题：

• 表面是子序列问题
• 实际是在找“趋势变化点”

这类题在真实工程中非常常见，比如：

• 股票涨跌节奏分析
• 用户行为拐点检测
• 实时信号抖动判断