摆动序列 图解题解

摆动序列到底指什么，要返回什么

摆动序列指这样的子序列：相邻两个数的差严格地正负交替，一个升一个降来回摆。子序列是从原数组里删掉任意几个数、剩下的按原顺序排。题目给一个数组 nums，问最长的摆动子序列有多长。题面例子 nums=[1,7,4,9,2,5]，整个数组本身就升降升降，答案是 6。

把所有子序列都试一遍，为什么不行

子序列能删任意个数，[1,7,4,9,2,5] 这 6 个数就有 2 的 6 次方种删法，把每一种都拿出来检查是不是摆动、再挑最长的，数组一长这个数量就爆炸，根本扫不完。得找个只扫一遍的办法。

为什么只数方向翻转的转折点就够

一段连续同方向（比如连着上升）的数里，只有两头的极值对摆动有用，中间那些台阶留着不会让交替变多，删掉也不破坏前后的正负交替。所以把每段同方向压成一个转折点，剩下的峰谷交替出现，就是最长的摆动子序列——落到操作上，只要在差的符号由正翻负、或由负翻正时把长度加一就够了。

这样贪着数不会亏：每段留住最靠后的那个峰或谷，等于给后面留了最大的回旋余地，接下来无论要接升还是接降都最容易接上。中间被删的台阶换成任何一个，后面能接的长度都不会更长。

两个变量 length 和 prev 怎么配合

落到代码上只要两个变量。length 从 1 起步，因为第一个数天然是子序列的起点；prev 记上一段的方向，初值 0 表示还没定方向。从第二个数起，算相邻差 diff=nums[i]-nums[i-1]：diff＞0 且 prev≤0，说明刚翻成升，length 加一、prev 记成 1；diff＜0 且 prev≥0，说明刚翻成降，length 加一、prev 记成 -1；diff 等于 0 或和上一段同方向，就跳过、prev 不动。

[1,7,4,9,2,5] 一步步数出 6

拿题面的 [1,7,4,9,2,5] 走一遍。length=1、prev=0。到 7，diff=6＞0 且 prev≤0，翻成升，length=2、prev=1。到 4，diff=-3＜0 且 prev≥0，翻成降，length=3、prev=-1。到 9，diff=5＞0，又翻成升，length=4、prev=1。到 2，diff=-7＜0，翻成降，length=5、prev=-1。到 5，diff=3＞0，翻成升，length=6。整个数组升降交替，答案就是 6。

哪几步一疏忽就把长度算多

差是 0 的那一步得当平台阶跳过，一旦把它算成一次方向，长度会凭空多一格。同方向连着几个台阶也只在第一次翻转时加过一次，后面的台阶再加就重复计了。prev 的初值也不能设成 1 或 -1，设死了方向，开头第一个峰或谷会被误判漏掉，从 0 起才让第一步自由定向。单个数或全部相等的数组，长度就是 1。

Python

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)
    length = 1                 # nums[0] 起点
    prev = 0                   # 上一段方向 +1/-1/0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i-1]
        if diff > 0 and prev <= 0:   # 翻成升
            length += 1; prev = 1
        elif diff < 0 and prev >= 0: # 翻成降
            length += 1; prev = -1
        # 平 或 同方向 → 跳过
    return length

C++

int wiggleMaxLength(vector<int>& nums){
    if(nums.size() < 2) return nums.size();
    int length = 1, prev = 0;     // prev:+1/-1/0
    for(int i = 1; i < (int)nums.size(); i++){
        int diff = nums[i] - nums[i-1];
        if(diff > 0 && prev <= 0){ length++; prev = 1; }
        else if(diff < 0 && prev >= 0){ length++; prev = -1; }
        // diff==0 或 同方向 → 跳过
    }
    return length;
}

Java

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) return nums.length;
        int length = 1, prev = 0;        // prev:+1/-1/0
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if (diff > 0 && prev <= 0) { length++; prev = 1; }
            else if (diff < 0 && prev >= 0) { length++; prev = -1; }
            // diff == 0 或 同方向 → 跳过
        }
        return length;                   // 摆动子序列长度
    }
}