LeetCode 376. 摆动序列
目录
题目描述
题意分析
给一个整数数组，要在里面挑出一个子序列（可以删元素，但保留的元素必须维持原有先后顺序），使得这个子序列中相邻两数的差正负交替，求这种子序列的最大长度。
定义上有两处容易读漏。其一，差值为 0 既不算正也不算负，所以相等的相邻元素不能同时留在子序列里。其二，长度为 1 的序列没有差值，题目约定它也是摆动序列；长度为 2 且两数不等的序列同样是摆动序列。
约束信号：数组长度上限 1000，元素范围 $[0, 1000]$。规模不大，$O(n^2)$ 也能过，但题目进阶明确要求 $O(n)$ 一趟解决，说明存在只依赖相邻关系的递推。
边界情况：只有一个元素时答案为 1；所有元素全部相等时，最多只能留一个，答案仍是 1；元素单调递增或递减时，只能留首尾两个，答案是 2。
解法：峰谷贪心
核心思路
摆动序列真正关心的不是差值大小，而是非零差值的符号能否在正、负之间交替。因此可以把数组看成若干段连续上升或连续下降的趋势，最优子序列只需保留每段交界处的「峰」和「谷」。
为什么趋势中间的点可以丢掉？假设一段一直上升，在其中多选两个元素只会得到两个同为正的差，无法增加摆动次数。把已选的末尾替换成这段最右侧、也是最大的元素，不会破坏前一次上升，反而更容易与后面的较小元素形成下降。连续下降时对称地保留更小的谷点。这个替换过程不减少任何可行解的长度，所以只数峰谷就能得到最优解。
实现时用
prevDiff记录上一个已纳入答案的非零差值方向，answer从 1 开始。当前差值为正且prevDiff <= 0时，说明遇到第一次上升或从下降转为上升；当前差值为负且prevDiff >= 0时则对称。只有这两种情况才让答案加一，差值为 0 直接忽略。正确性：上面的替换论证说明，任意最优解都能在不变短的前提下，被改造成只包含首元素和峰谷的子序列；算法恰好在每次趋势反转时选中一个新峰或新谷，构造出同样长的可行解。因此它既不会少选，也不可能超过最优值。
解题步骤
- 初始化
answer = 1、prevDiff = 0。单个元素已是长度为 1 的摆动序列，0 表示尚未出现有效方向。- 从下标 1 开始，计算相邻差
diff = nums[i] - nums[i - 1]。- 若
diff > 0 && prevDiff <= 0，当前元素形成第一段上升或新峰，令answer++，并记录这次正差值。- 若
diff < 0 && prevDiff >= 0，当前元素形成第一段下降或新谷，同样累加答案并更新prevDiff。- 若差值为 0，或者与
prevDiff同号，不增加长度：前者不是摆动，后者只是把当前趋势的峰或谷向后推。- 遍历结束后返回
answer。例如
nums = [1,7,7,4,9,2,5]，非零差值方向依次为「正、负、正、负、正」，中间的零差值被忽略。算法选出[1,7,4,9,2,5]，答案为 6。
代码实现
class Solution {
public int wiggleMaxLength(int[] nums) {
int answer = 1;
int prevDiff = 0;
for (int i = 1; i < nums.length; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
answer++;
prevDiff = diff;
}
}
return answer;
}
}
func wiggleMaxLength(nums []int) int {
answer, prevDiff := 1, 0
for i := 1; i < len(nums); i++ {
diff := nums[i] - nums[i-1]
if (diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0) {
answer++
prevDiff = diff
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。只顺序扫描一次数组。
- 空间复杂度：$O(1)$。只使用答案、当前差值和上一个有效差值等常数变量。
关键点总结
- 把问题转换为「统计非零差值的符号变化」，就能从子序列枚举转向线性扫描。
- 贪心选峰谷的依据是替换论证：上升段保留更大的末尾，下降段保留更小的末尾，都不会让后续选择变差。
prevDiff只需要保留上一个有效方向；连续同号的差值不会增加摆动长度。- 零差值既不是上升也不是下降，必须跳过，且不能清空之前的有效方向。
- 面试时先讲「单调段内中间点无贡献」，再讲「保留更极端的末尾」，就能完整回答贪心选择为什么正确。
易错点总结
- 把零差值当成一次摆动：
[1,1,1]的正确答案是 1，不能用>=或<=把相等元素归入上升、下降。- 遇到相等元素就把
prevDiff清零：[1,3,3,5]会把同一段上升计数两次，错误返回 3，正确答案是 2。- 忽略第一个非零差值：若判断条件写成
prevDiff < 0或prevDiff > 0，初值 0 无法进入任一分支，[1,2]会错误返回 1。- 连续同向时也累加答案：
[1,2,3]只能选首尾两个元素；两个正差值不交替，答案不是 3。- 把子序列误当成连续子数组：
[1,17,5,10,13,15,10,5,16,8]可以删去中间的同向元素得到长度 7，不能只统计最长连续摆动段。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 122. 买卖股票的最佳时机 II | 中等 | 同样识别波峰波谷，但求差值累加而非计数 |
| 300. 最长递增子序列 | 中等 | 单一方向约束，需贪心加二分才能降到对数 |
| 845. 数组中的最长山脉 | 中等 | 要求连续子数组且只允许先升后降一次 |
| 53. 最大子数组和 | 中等 | 滚动 DP 求和的最值，状态只有一维 |