376. 摆动序列

题目描述

对一个数字序列，计算每对相邻元素的差。如果这些差严格地一正一负交替出现，就称它为摆动序列。第一个差是正是负都可以。差为 0 不算正也不算负，会破坏摆动。

只有一个元素的序列，以及只有两个不相等元素的序列，也算摆动序列。

子序列是从原数组中删掉若干个元素（也可以不删）后，剩下元素按原顺序组成的序列。

输入整数数组 nums，返回其中最长的摆动子序列的长度。

示例 1

输入：nums = [1,7,4,9,2,5]
输出：6

解释：相邻差为 6,-3,5,-7,3，正负交替，整个数组就是答案。

示例 2

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7

解释：例如 [1,17,10,13,10,16,8]，差为 16,-7,3,-3,6,-8。

示例 3

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

解释：数组一路递增，最多只能取两个元素。

数据范围

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

进阶：能否在 O(n) 时间内解决？

解题思路：上升下降双状态

维护两个量：up 是以“上升”结尾的最长摆动子序列长度，down 是以“下降”结尾的。遇到 nums[i] > nums[i-1]，可以接在下降结尾的序列后：up = down + 1；遇到下降则 down = up + 1；相等时都不变。直观上就是统计折线的峰和谷。

为什么正确

处理完 nums[0..i] 后，up/down 分别是该前缀中最后一步为上升/下降的最长摆动子序列长度。

复杂度分析

时间 O(n)，空间 O(1)。

易错点

差为 0 的相邻元素不算摆动，必须跳过；序列全部相等时答案是 1，不是 0。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        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)

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1])
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }
        return Math.max(up, down);
    }
}

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int up = 1, down = 1;
        for (int i = 1; i < (int)nums.size(); i++) {
            if (nums[i] > nums[i - 1])
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }
        return max(up, down);
    }
};

func wiggleMaxLength(nums []int) int {
	up, down := 1, 1
	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[i-1] {
			up = down + 1
		} else if nums[i] < nums[i-1] {
			down = up + 1
		}
	}
	return max(up, down)
}

var wiggleMaxLength = function(nums) {
    let up = 1, down = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1])
            up = down + 1;
        else if (nums[i] < nums[i - 1])
            down = up + 1;
    }
    return Math.max(up, down);
};

function wiggleMaxLength(nums: number[]): number {
    let up = 1, down = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1])
            up = down + 1;
        else if (nums[i] < nums[i - 1])
            down = up + 1;
    }
    return Math.max(up, down);
}

载入编辑器，自己跑一遍 →

其他解法

O(n²) 动态规划是最直接的状态定义；主解法把它压缩成两个变量的 O(n) 递推；贪心统计峰谷与主解法同为 O(n)，换成了几何视角。

解法 2：贪心统计峰谷时间 O(n)，空间 O(1)

摆动子序列的最长长度等于序列中峰和谷的个数加上两个端点。记录上一个非零差值 prevdiff。当前差值 diff 与 prevdiff 符号相反（prevdiff 为 0 时视为可接任意方向）就把答案加一，并更新 prevdiff。相等的相邻元素直接跳过。

从几何角度解释答案，直观易懂。正确性依赖“保留每段单调区间的端点最优”这一论证，而双状态动态规划的转移更容易严格证明。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n
        prevdiff = nums[1] - nums[0]
        ans = 2 if prevdiff != 0 else 1
        for i in range(2, n):
            diff = nums[i] - nums[i - 1]
            if (diff > 0 and prevdiff <= 0) or (diff < 0 and prevdiff >= 0):
                ans += 1
                prevdiff = diff
        return ans

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) return n;
        int prevdiff = nums[1] - nums[0];
        int ans = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ans++;
                prevdiff = diff;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        int prevdiff = nums[1] - nums[0];
        int ans = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ans++;
                prevdiff = diff;
            }
        }
        return ans;
    }
};

func wiggleMaxLength(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}
	prevdiff := nums[1] - nums[0]
	ans := 1
	if prevdiff != 0 {
		ans = 2
	}
	for i := 2; i < n; i++ {
		diff := nums[i] - nums[i-1]
		if (diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0) {
			ans++
			prevdiff = diff
		}
	}
	return ans
}

var wiggleMaxLength = function(nums) {
    const n = nums.length;
    if (n < 2) return n;
    let prevdiff = nums[1] - nums[0];
    let ans = prevdiff !== 0 ? 2 : 1;
    for (let i = 2; i < n; i++) {
        const diff = nums[i] - nums[i - 1];
        if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
            ans++;
            prevdiff = diff;
        }
    }
    return ans;
};

function wiggleMaxLength(nums: number[]): number {
    const n = nums.length;
    if (n < 2) return n;
    let prevdiff = nums[1] - nums[0];
    let ans = prevdiff !== 0 ? 2 : 1;
    for (let i = 2; i < n; i++) {
        const diff = nums[i] - nums[i - 1];
        if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
            ans++;
            prevdiff = diff;
        }
    }
    return ans;
}

解法 3：O(n²) 动态规划时间 O(n²)，空间 O(n)

up[i] 表示以 nums[i] 结尾、最后一步上升的最长摆动子序列长度，down[i] 表示最后一步下降的长度，初值都是 1。对每个 j < i，若 nums[j] < nums[i]，用 down[j] + 1 更新 up[i]；若 nums[j] > nums[i]，用 up[j] + 1 更新 down[i]。答案是所有 up[i]、down[i] 的最大值。

和最长递增子序列的写法一致，状态定义最自然。n 较大时 O(n²) 偏慢；观察到只需看前一个元素后，就能优化成主解法。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        up = [1] * n
        down = [1] * n
        best = 1 if n else 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    up[i] = max(up[i], down[j] + 1)
                elif nums[j] > nums[i]:
                    down[i] = max(down[i], up[j] + 1)
            best = max(best, up[i], down[i])
        return best

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] up = new int[n], down = new int[n];
        int best = n > 0 ? 1 : 0;
        for (int i = 0; i < n; i++) {
            up[i] = 1;
            down[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) up[i] = Math.max(up[i], down[j] + 1);
                else if (nums[j] > nums[i]) down[i] = Math.max(down[i], up[j] + 1);
            }
            best = Math.max(best, Math.max(up[i], down[i]));
        }
        return best;
    }
}

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> up(n, 1), down(n, 1);
        int best = n ? 1 : 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) up[i] = max(up[i], down[j] + 1);
                else if (nums[j] > nums[i]) down[i] = max(down[i], up[j] + 1);
            }
            best = max(best, max(up[i], down[i]));
        }
        return best;
    }
};

func wiggleMaxLength(nums []int) int {
	n := len(nums)
	up := make([]int, n)
	down := make([]int, n)
	best := 0
	if n > 0 {
		best = 1
	}
	for i := 0; i < n; i++ {
		up[i], down[i] = 1, 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				up[i] = max(up[i], down[j]+1)
			} else if nums[j] > nums[i] {
				down[i] = max(down[i], up[j]+1)
			}
		}
		best = max(best, up[i], down[i])
	}
	return best
}

var wiggleMaxLength = function(nums) {
    const n = nums.length;
    const up = new Array(n).fill(1), down = new Array(n).fill(1);
    let best = n ? 1 : 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) up[i] = Math.max(up[i], down[j] + 1);
            else if (nums[j] > nums[i]) down[i] = Math.max(down[i], up[j] + 1);
        }
        best = Math.max(best, up[i], down[i]);
    }
    return best;
};

function wiggleMaxLength(nums: number[]): number {
    const n = nums.length;
    const up: number[] = new Array(n).fill(1), down: number[] = new Array(n).fill(1);
    let best = n ? 1 : 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) up[i] = Math.max(up[i], down[j] + 1);
            else if (nums[j] > nums[i]) down[i] = Math.max(down[i], up[j] + 1);
        }
        best = Math.max(best, up[i], down[i]);
    }
    return best;
}

贪心专题的其他题目

查看贪心全部题目 →