文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 先用直觉理解摆动序列
- 贪心的关键点
- Swift 可运行 Demo 代码
- 代码逐行拆解
- 1. 为什么 `up` 和 `down` 初始值是 1
- 2. 为什么可以直接覆盖 `up` / `down`
- 3. 为什么可以忽略相等的情况
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结
摘要
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 转向贪心”的题：
- 表面是子序列问题
- 实际是在找“趋势变化点”
这类题在真实工程中非常常见，比如：
- 股票涨跌节奏分析
- 用户行为拐点检测
- 实时信号抖动判断
