摆动序列如何用贪心求最长长度？（LeetCode 376）

简化版

最长摆动序列只需要数「符号变化」：相邻差值从正变负或从负变正，就形成一个新的摆动点。

跳过差值为 0 的相邻元素，维护上一个非零差值 prevDiff；当前差值 curDiff 与 prevDiff 符号相反时，答案加 1，并更新 prevDiff。

详细版

摆动序列要求相邻差值正负交替。为了得到最长长度，我们不需要保留单调段中的所有点，只需要保留每段单调趋势的端点，也就是峰和谷。

如果当前差值和上一个有效差值符号相反，说明出现了一个新的峰或谷，长度可以加 1。如果符号相同，说明仍在同一段单调趋势中，中间点可以舍弃，因为保留更极端的端点不会让未来更差。

int wiggleMaxLength(int[] nums) {
    if (nums.length < 2) return nums.length;
    int ans = 1;
    int prevDiff = 0;
    for (int i = 1; i < nums.length; i++) {
        int curDiff = nums[i] - nums[i - 1];
        if ((curDiff > 0 && prevDiff <= 0) || (curDiff < 0 && prevDiff >= 0)) {
            ans++;
            prevDiff = curDiff;
        }
    }
    return ans;
}

完整版教学

一、摆动序列到底在数什么

摆动序列关心的是相邻差值的符号，而不是数值大小。比如 [1,7,4,9,2,5] 的差值是 [+6,-3,+5,-7,+3]，符号正负交替，所以长度为 6。相反，[1,2,3,4] 的差值都是正，只能选两个点形成长度 2 的摆动序列。

因此问题可以转化为：从数组中挑一些点，让相邻选中点之间的差值符号尽量多地交替。单调段里的多个中间点不会产生额外符号变化，真正有价值的是趋势拐点。

二、为什么峰谷可以代表整段单调趋势

如果一段连续上升，例如 1,3,5,8，这些点之间的差值都是正。为了和后面的下降形成摆动，只保留上升段最后的最大值 8 最有利，因为它更容易和后面的较小值形成负差。保留中间的 3 或 5 不会增加当前摆动次数，也不会比保留 8 更好。

下降段同理，只保留最低的谷值更好。这个「单调段只留端点」就是贪心依据：中间点没有贡献，可以安全丢掉。

三、符号变化时为什么答案加一

把序列看成折线，摆动点就是折线的峰或谷。当前差值从正变负，说明刚刚经过一个峰；从负变正，说明刚刚经过一个谷。每出现一次这样的趋势反转，最长摆动子序列就能多保留一个点。

上升后下降:  1 -> 7 -> 4
              +    -
              7 是峰，可以计入

下降后上升:  9 -> 2 -> 5
              -    +
              2 是谷，可以计入

初始化答案为 1，表示至少可以选第一个数。每遇到一次有效趋势，选入当前点，答案加 1。

四、差值为 0 为什么要跳过

相等元素不会形成正差或负差，也不能帮助摆动。例如 [1,1,1,2] 中，前几个 1 对摆动没有贡献，真正的有效差值只有最后的正差。若把 0 当成一种符号，会错误地认为 1,1,2 有两次变化。

所以 curDiff == 0 时不更新 prevDiff。只有当前差值非零，并且相对上一个非零差值发生符号变化时，才计入答案。

五、数字例子走一遍

以 nums = [1, 7, 4, 9, 2, 5] 为例：

i	curDiff	prevDiff 变化	ans
1	`+6`	`0 -> +6`	2
2	`-3`	`+6 -> -3`	3
3	`+5`	`-3 -> +5`	4
4	`-7`	`+5 -> -7`	5
5	`+3`	`-7 -> +3`	6

每一步都有符号反转，所以整个数组都是摆动序列。若输入 [1, 4, 7, 2, 5]，前两段都是正差，4 可被舍弃，最长为 [1,7,2,5]。

六、和动态规划写法的关系

这题也有 DP 写法：up[i] 表示以 i 结尾、最后趋势向上的最长长度，down[i] 表示最后趋势向下的最长长度。转移是 nums[i] > nums[i-1] 时 up = down + 1，反之 down = up + 1。

贪心写法其实是把 DP 进一步压缩成「只在趋势变化时更新」。因为同一趋势连续出现时，保留更极端的端点不会变差，所以不用保留所有状态。面试里可以先讲峰谷贪心，再补一句它和 up/down DP 等价。

易错点：这题不是求连续子数组，而是子序列；可以删除中间点，所以单调段中间元素才可以被贪心丢掉。

七、常见误区与追问

误区：把差值为 0 当作一次摆动。 相等元素没有方向，必须跳过。
误区：认为必须连续选择元素。 题目是子序列，可以删除元素。
误区：符号相同时立即更新答案。 同一单调段不会增加摆动次数，只需要替换端点。
追问：为什么保留上升段最大值更优？ 它更容易和后面的下降形成更大的负差，不会减少未来选择。
追问：复杂度是多少？ 单次扫描，时间 O(n)，空间 O(1)。
追问：DP 和贪心哪个更推荐？ 面试求最优解释时讲贪心；如果面试官要求状态转移，可补充 up/down DP。

八、加强记忆

摆动序列的记忆锚点是「数峰谷，不数中间坡」。连续上升或连续下降只贡献一个趋势，中间点不产生新摆动，可以被更极端的端点替换。当前非零差值与上一个非零差值符号相反时，就出现一个新峰或新谷，答案加一。抓住「符号变化才加分，零差跳过，同号延续趋势」三件事，就能稳定写出贪心解。

简化版

详细版