文章目录
-
- 摘要
- 描述
- 题解答案
- 题解代码分析
-
- 先用直觉理解摆动序列
- 贪心的关键点
- 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 代码
class Solution {
func wiggleMaxLength(_ nums: [Int]) -> Int {
if nums.count < 2 {
return nums.count
}
// up 表示以“上升”结尾的最长摆动序列
// down 表示以“下降”结尾的最长摆动序列
var up = 1
var down = 1
for i in 1..<nums.count {
if nums[i] > nums[i – 1] {
// 出现上升趋势
up = down + 1
} else if nums[i] < nums[i – 1] {
// 出现下降趋势
down = up + 1
}
// 相等的情况直接跳过
}
return max(up, down)
}
}
代码逐行拆解
1. 为什么 up 和 down 初始值是 1
因为：
- 单个元素本身就是摆动序列
- 不需要任何差值
2. 为什么可以直接覆盖 up / down
这是这道题最“反直觉”的地方。
原因在于：
- 我们只关心 “最长”
- 一旦出现新的趋势变化
- 更短的历史路径已经没有任何价值了
这就是贪心成立的根本原因。
3. 为什么可以忽略相等的情况
因为：
差值 = 0
既不是正数，也不是负数， 无法构成摆动的一部分，跳过即可。
示例测试及结果
let solution = Solution()
print(solution.wiggleMaxLength([1,7,4,9,2,5]))
// 6
print(solution.wiggleMaxLength([1,17,5,10,13,15,10,5,16,8]))
// 7
print(solution.wiggleMaxLength([1,2,3,4,5,6,7,8,9]))
// 2
输出结果：
6
7
2
与题目示例完全一致。
时间复杂度
只遍历一次数组：
O(n)
这是题目进阶要求的最优解。
空间复杂度
只使用了常量级变量：
O(1)
非常适合在性能敏感场景中使用。
总结
LeetCode 376 是一道非常典型的“从 DP 转向贪心”的题：
- 表面是子序列问题
- 实际是在找“趋势变化点”
这类题在真实工程中非常常见，比如：
- 股票涨跌节奏分析
- 用户行为拐点检测
- 实时信号抖动判断
