题目描述
相邻差值正负交替(升、降、升、降…)的序列叫摆动序列。求最长摆动子序列的长度。
思路解析
把每个子序列都挑出来、逐一检查是不是一上一下交替，一共 2ⁿ 个，指数级。其实根本不用枚举——最长摆动子序列的长度，等于原序列里方向转折的次数 + 1，一遍扫描数转折就行。
关键招：up = 目前以「上升」结尾的最长摆动长度，down = 以「下降」结尾的。遇上升 up = down + 1(接在一段下降之后)，遇下降 down = up + 1，相等则都不变。答案取两者最大。为什么对：每次真正改方向才接上一节，同方向连走不算新转折，所以同方向时长度不增长。
起点：从第一个数开始，up 和 down 都是 1：单独一个元素本身就是长度 1 的摆动序列。
i=1 · 7 大于 1 上升：7 比前一个 1 大，是上升。up 接在「下降段 down」后面：up = down + 1 = 2。down 不变。
i=2 · 4 小于 7 下降：4 比 7 小，是下降——方向转折了。down 接在刚才的 up 后面：down = up + 1 = 3。
i=3 · 9 大于 4 上升：9 比 4 大，又转回上升。up = down + 1 = 4。
i=4 · 2 小于 9 下降：2 比 9 小，再次转折成下降。down = up + 1 = 5。
i=5 · 5 大于 2 上升：5 比 2 大，又转上升。up = down + 1 = 6。每一步都在转折，长度一路往上涨。
答案：整段每一步都在转折，up 涨到 6、down 涨到 5。答案取两者最大 = 6，正好是全长。
负例 · 换成 [1,3,5,4,2,6]：负例分支：换个数组，开头 1→3→5 连续两次上升、没转折。i=2 时 5 大于 3 仍是升，up = down + 1 算出来还是 2，长度原地不动——同方向连走不增长，这正是「只在转折时 +1」的体现。
最长摆动子序列的长度 = 方向转折点个数 + 1。把「当前方向」当状态来维护，这是贪心 / 状态机的常见套路。
参考代码（Python）
1if len(nums) < 2:
2 return len(nums) # 空或单元素直接返回长度
3up = down = 1
4for i in range(1, len(nums)):
5 if nums[i] > nums[i-1]: # 上升
6 up = down + 1
7 elif nums[i] < nums[i-1]: # 下降
8 down = up + 1
9 # 相等：up、down 都不变
10return max(up, down)复杂度分析
- 时间复杂度：O(n) —— 只扫一遍、每个元素比较一次相邻差
- 空间复杂度：O(1) —— 只用 up、down 两个变量
套路模板
记住骨架：两个状态此消彼长、只在方向改变时 +1。买卖股票 II「只在上涨段累加」也是这种一遍状态贪心。
1# 把「方向 / 状态」当变量，一遍扫描交替更新
2up = down = 1
3for i in range(1, n):
4 if nums[i] > nums[i-1]: # 升：接在降后面
5 up = down + 1
6 elif nums[i] < nums[i-1]: # 降：接在升后面
7 down = up + 1
8 # 相等：两者都不动
9return max(up, down)易错点
- 错误写法：相邻相等(==)时也更新 up / down → 正确写法：相等时 up、down 都保持不变（相等既不算上升也不算下降，不构成转折；当成上升或下降会把长度多算，如 [1,1,2] 应是 2 却被算成 3）
- 错误写法：同方向连续上升时让 up 一直加 → 正确写法：同方向时 up = down + 1 自然保持不变（down 没变、up 重算还是同一个值，长度不增长——这正是「只在转折时增长」，连走不算新摆动）
- 错误写法：长度 小于 2 不特判直接进循环 → 正确写法：先处理 len 小于 2 直接返回该长度（空数组或单元素没有相邻对可比，单元素本身也是合法摆动序列，长度应为它自己）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。