LeetCode 376中等贪心
摆动序列 图解题解
这道题到底在问什么
相邻差值正负交替(升、降、升、降…)的序列叫摆动序列。求最长摆动子序列的长度。
- nums
- [1, 7, 4, 9, 2, 5]
- 输出
- 6 （整段本身就在一上一下交替）
先想最直接的笨办法
把每个子序列都挑出来、逐一检查是不是一上一下交替，一共 2ⁿ 个，指数级。其实根本不用枚举——最长摆动子序列的长度，等于原序列里方向转折的次数 + 1，一遍扫描数转折就行。（动画第 3 步）
最优解：一步一步想明白
- 3把每个子序列都挑出来、逐一检查是不是一上一下交替，一共 2ⁿ 个，指数级。其实根本不用枚举——最长摆动子序列的长度，等于原序列里方向转折的次数 + 1，一遍扫描数转折就行。
- 4关键招：up = 目前以「上升」结尾的最长摆动长度，down = 以「下降」结尾的。遇上升 up = down + 1(接在一段下降之后)，遇下降 down = up + 1，相等则都不变。答案取两者最大。为什么对：每次真正改方向才接上一节，同方向连走不算新转折，所以同方向时长度不增长。
- 5up=1, down=1从第一个数开始，up 和 down 都是 1：单独一个元素本身就是长度 1 的摆动序列。
- 6up = down+1 = 27 比前一个 1 大，是上升。up 接在「下降段 down」后面：up = down + 1 = 2。down 不变。
- 7down = up+1 = 34 比 7 小，是下降——方向转折了。down 接在刚才的 up 后面：down = up + 1 = 3。
- 8up = down+1 = 49 比 4 大，又转回上升。up = down + 1 = 4。
- 9down = up+1 = 52 比 9 小，再次转折成下降。down = up + 1 = 5。
- 10up = down+1 = 65 比 2 大，又转上升。up = down + 1 = 6。每一步都在转折，长度一路往上涨。
- 11max(up, down) = 6整段每一步都在转折，up 涨到 6、down 涨到 5。答案取两者最大 = 6，正好是全长。
- 12i=2：5 大于 3，同方向负例分支：换个数组，开头 1→3→5 连续两次上升、没转折。i=2 时 5 大于 3 仍是升，up = down + 1 算出来还是 2，长度原地不动——同方向连走不增长，这正是「只在转折时 +1」的体现。
- 15最长摆动子序列的长度 = 方向转折点个数 + 1。把「当前方向」当状态来维护，这是贪心 / 状态机的常见套路。
⚠️ 容易写错的地方
✗ 错：相邻相等(==)时也更新 up / down
✓ 对：相等时 up、down 都保持不变
相等既不算上升也不算下降，不构成转折；当成上升或下降会把长度多算，如 [1,1,2] 应是 2 却被算成 3
✗ 错：同方向连续上升时让 up 一直加
✓ 对：同方向时 up = down + 1 自然保持不变
down 没变、up 重算还是同一个值，长度不增长——这正是「只在转折时增长」，连走不算新摆动
✗ 错：长度 小于 2 不特判直接进循环
✓ 对：先处理 len 小于 2 直接返回该长度
空数组或单元素没有相邻对可比，单元素本身也是合法摆动序列，长度应为它自己
完整代码（Python）
Python
class Solution:
def wiggleMaxLength(self, nums):
if len(nums) < 2:
return len(nums)
up = down = 1
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
up = down + 1
elif nums[i] < nums[i - 1]:
down = up + 1
return max(up, down)套路模板 · 双状态贪心「up / down 交替更新」（背下来）
# 把「方向 / 状态」当变量，一遍扫描交替更新
up = down = 1
for i in range(1, n):
if nums[i] > nums[i-1]: # 升：接在降后面
up = down + 1
elif nums[i] < nums[i-1]: # 降：接在升后面
down = up + 1
# 相等：两者都不动
return max(up, down)复杂度
时间复杂度
O(n)
只扫一遍、每个元素比较一次相邻差
空间复杂度
O(1)
只用 up、down 两个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 摆动序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「贪心」，换最直接的暴力解会差在哪？+
贪心抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。