题目描述
思路解析
一句话答案：LeetCode 376 摆动序列：求相邻差正负交替的最长子序列长度，贪心数方向翻转——每翻一次方向长度加一、平和同方向跳过，一遍扫完，时间 O(n)、空间 O(1)。
摆动序列到底指什么，要返回什么
摆动序列指这样的子序列：相邻两个数的差严格地正负交替，一个升一个降来回摆。子序列是从原数组里删掉任意几个数、剩下的按原顺序排。题目给一个数组 nums，问最长的摆动子序列有多长。题面例子 nums=[1,7,4,9,2,5]，整个数组本身就升降升降，答案是 6。
把所有子序列都试一遍，为什么不行
子序列能删任意个数，[1,7,4,9,2,5] 这 6 个数就有 2 的 6 次方种删法，把每一种都拿出来检查是不是摆动、再挑最长的，数组一长这个数量就爆炸，根本扫不完。得找个只扫一遍的办法。
为什么只数方向翻转的转折点就够
一段连续同方向（比如连着上升）的数里，只有两头的极值对摆动有用，中间那些台阶留着不会让交替变多，删掉也不破坏前后的正负交替。所以把每段同方向压成一个转折点，剩下的峰谷交替出现，就是最长的摆动子序列——落到操作上，只要在差的符号由正翻负、或由负翻正时把长度加一就够了。
这样贪着数不会亏：每段留住最靠后的那个峰或谷，等于给后面留了最大的回旋余地，接下来无论要接升还是接降都最容易接上。中间被删的台阶换成任何一个，后面能接的长度都不会更长。
两个变量 length 和 prev 怎么配合
落到代码上只要两个变量。length 从 1 起步，因为第一个数天然是子序列的起点；prev 记上一段的方向，初值 0 表示还没定方向。从第二个数起，算相邻差 diff=nums[i]-nums[i-1]：diff＞0 且 prev≤0，说明刚翻成升，length 加一、prev 记成 1；diff＜0 且 prev≥0，说明刚翻成降，length 加一、prev 记成 -1；diff 等于 0 或和上一段同方向，就跳过、prev 不动。
[1,7,4,9,2,5] 一步步数出 6
拿题面的 [1,7,4,9,2,5] 走一遍。length=1、prev=0。到 7，diff=6＞0 且 prev≤0，翻成升，length=2、prev=1。到 4，diff=-3＜0 且 prev≥0，翻成降，length=3、prev=-1。到 9，diff=5＞0，又翻成升，length=4、prev=1。到 2，diff=-7＜0，翻成降，length=5、prev=-1。到 5，diff=3＞0，翻成升，length=6。整个数组升降交替，答案就是 6。
哪几步一疏忽就把长度算多
差是 0 的那一步得当平台阶跳过，一旦把它算成一次方向，长度会凭空多一格。同方向连着几个台阶也只在第一次翻转时加过一次，后面的台阶再加就重复计了。prev 的初值也不能设成 1 或 -1，设死了方向，开头第一个峰或谷会被误判漏掉，从 0 起才让第一步自由定向。单个数或全部相等的数组，长度就是 1。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条「只数方向真正改变的峰和谷，平的和同方向的跳过」——下面每一帧都在套它。
第一个数 1 永远算摆动子序列的起点，长度从 1 起步。现在方向还没确定，等下一个数来定升还是降。
算出差 16，本段方向是「升 ↑」。和上一段方向「（还没定方向）」比一比：不一样，方向要翻转了。
方向真的翻转了！把 nums[1]=17 选作新的峰（局部最高）（绿色高亮），摆动长度涨到 2。
算出差 -12，本段方向是「降 ↓」。和上一段方向「升 ↑」比一比：不一样，方向要翻转了。
方向真的翻转了！把 nums[2]=5 选作新的谷（局部最低）（绿色高亮），摆动长度涨到 3。
算出差 5，本段方向是「升 ↑」。和上一段方向「降 ↓」比一比：不一样，方向要翻转了。
方向真的翻转了！把 nums[3]=11 选作新的峰（局部最高）（绿色高亮），摆动长度涨到 4。
算出差 3，本段方向是「升 ↑」。和上一段方向「升 ↑」比一比：一样，是同方向的台阶。
同方向的延续，跳过 nums[4]，不进子序列，长度仍是 4。
算出差 2，本段方向是「升 ↑」。和上一段方向「升 ↑」比一比：一样，是同方向的台阶。
同方向的延续，跳过 nums[5]，不进子序列，长度仍是 4。
算出差 -5，本段方向是「降 ↓」。和上一段方向「升 ↑」比一比：不一样，方向要翻转了。
方向真的翻转了！把 nums[6]=10 选作新的谷（局部最低）（绿色高亮），摆动长度涨到 5。
算出差 -5，本段方向是「降 ↓」。和上一段方向「降 ↓」比一比：一样，是同方向的台阶。
同方向的延续，跳过 nums[7]，不进子序列，长度仍是 5。
算出差 11，本段方向是「升 ↑」。和上一段方向「降 ↓」比一比：不一样，方向要翻转了。
方向真的翻转了！把 nums[8]=16 选作新的峰（局部最高）（绿色高亮），摆动长度涨到 6。
算出差 -8，本段方向是「降 ↓」。和上一段方向「升 ↑」比一比：不一样，方向要翻转了。
方向真的翻转了！把 nums[9]=8 选作新的谷（局部最低）（绿色高亮），摆动长度涨到 7。
整趟扫完，绿色高亮的 7 个数 [1, 17, 5, 11, 10, 16, 8] 就是一条最长摆动子序列，长度 7。一次遍历搞定，时间 O(n)。
边界先想清：全相等只算 1，单个数也是 1，平台阶不贡献摆动。
两个高频追问，把「贪心为什么对」和「DP 等价解」串起来。
参考代码
def wiggleMaxLength(nums): if len(nums) < 2: return len(nums) length = 1 # nums[0] 起点 prev = 0 # 上一段方向 +1/-1/0 for i in range(1, len(nums)): diff = nums[i] - nums[i-1] if diff > 0 and prev <= 0: # 翻成升 length += 1; prev = 1 elif diff < 0 and prev >= 0: # 翻成降 length += 1; prev = -1 # 平 或 同方向 → 跳过 return length复杂度
- 时间：O(n)，一次遍历，每个数只看一次相邻差
- 空间：O(1)，只用 length 和 prev 两个变量
易错点
面试追问把动画讲成自己的话
追问除了贪心，还能怎么做？复杂度差别？
追问为什么贪心「只保留转折点」是对的？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
根据身高重建队列
LeetCode 406 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题