LeetCode 376. 摆动序列
题目描述
题意分析
从数组中按原顺序选择若干元素，使选出元素之间的相邻差值严格正负交替，返回最长长度。子序列可以跳过元素，不要求连续；第一个非零差值可以为正，也可以为负。
相等元素产生的零差值不能算一次摆动。单个元素本身是长度为 $1$ 的摆动序列，所以题目给定的非空数组至少有一个元素可选。
解法：峰谷贪心
核心思路
[!blue]
摆动只关心上升、下降是否交替，而不关心差值的绝对大小。把连续同方向的变化看成一段，在一段内继续向同方向移动，不能直接为摆动序列增加一个元素，否则相邻两次差值会同号。
但同方向移动可以让当前端点更有利：
- 正在上升时，用后面更高的点替换末尾的高点。它仍高于前一个低点，而且原来能接在旧高点后面的更低值，也一定低于新高点，因此不会失去后续下降的机会。
- 正在下降时，用后面更低的点替换末尾的低点。它仍低于前一个高点，并让后续上升至少同样容易。
所以可以把每段同方向变化压缩到最有利的端点，只在方向反转时增加长度，这样会保留交替的峰和谷。去掉零差值后，若共有
r段连续同号的方向，贪心便能选出r + 1个元素。这个长度也达到上限：子序列中任意一次上升或下降，在它跨过的原数组区间内，都至少需要一个同号的相邻差值。这些区间包含的相邻差值按顺序互不重叠，而相邻两次摆动方向相反，不可能由原数组中的同一个方向段提供。因此最多形成
r次摆动，即r + 1个元素。代码只求长度，不需要真的保存或替换这些端点。扫描到相邻差值
diff = nums[i] - nums[i - 1]时，用prevDiff保存此前接受的非零方向，只使用它的正负号：
diff > 0且prevDiff <= 0，开始了上升方向，答案加一。diff < 0且prevDiff >= 0，开始了下降方向，答案加一。- 差值同号时只是隐含替换当前端点；差值为 $0$ 时是平台，两者都不增加答案，也不改变已记录的方向。
初始
answer = 1、prevDiff = 0。零表示还没有方向，因此第一次遇到非零差值时也会增加答案，选出第二个元素。若数组只有一个元素或所有元素相等，就一直保留答案 $1$。平台不能把方向清零，否则平台之后同方向的延伸会被误当成一次新的摆动。
解题步骤
- 初始化
answer = 1、prevDiff = 0。- 从第二个元素开始，计算它与前一个元素的差值
diff。- 若
diff非零，且与prevDiff反号或prevDiff仍为零，令答案加一，并将prevDiff更新为diff。- 同方向和零差值直接略过；遍历结束后返回
answer。
代码实现
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)$，只保存方向和长度。
关键点总结
[!green]
- 上升段保留更高端点，下降段保留更低端点，不会减少后续反向选择的机会。
- 长度等于非零方向段数加一；只需要记录方向，无需构造实际子序列。
- 零差值既不计数，也不改变此前方向；
prevDiff = 0只负责接纳最初的非零差值。
易错点总结
[!yellow]
- 直接统计不相等的相邻对，会把连续上升算成多次摆动。
- 遇到相等值将方向清零，会把同方向的平台两侧重复计数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 原题要求一直递增，本题要求相邻差值符号交替，可压缩为上升/下降状态。 |
| 978. 最长湍流子数组 | 中等 | 原题要求连续区间，本题可跳过不利元素形成子序列，处理相等值和转折的方式不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！