What is a wiggle subsequence?

A wiggle subsequence alternates strictly between increasing and decreasing differences between consecutive elements.

Why do we use up and down states in DP for Wiggle Subsequence?

Up and down states capture the length of the longest subsequence ending with a positive or negative difference, essential for correct state transitions.

Can consecutive equal elements be part of the wiggle subsequence?

No, equal elements do not contribute to alternating differences and should be skipped in state updates.

What is the time complexity of the optimal solution?

The greedy linear pass solution achieves O(n) time by updating only two variables, up and down, per element.

How do I handle arrays of length 1 or 2?

An array of length 1 is trivially a wiggle sequence of length 1; a two-element array with unequal values forms a wiggle sequence of length 2.

#376

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现…

数组动态规划贪心

题目描述

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 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
解释：这个序列包含几个长度为 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) 时间复杂度完成此题?

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示以第 $i$ 个元素结尾且最后是上升趋势的摆动序列的长度，定义 $g[i]$ 表示以第 $i$ 个元素结尾且最后是下降趋势的摆动序列的长度。初始时 $f[0] = g[0] = 1$ ，因为只有一个元素时，摆动序列的长度为 $1$ 。初始化答案为 $1$ 。

对于 $f[i]$ ，其中 $i \geq 1$ ，我们在 $[0, i)$ 的范围内枚举 $j$ ，如果 $nums[j] < nums[i]$ ，则说明 $i$ 可以接在 $j$ 的后面形成一个上升的摆动序列，此时 $f[i] = \max(f[i], g[j] + 1)$ ；如果 $nums[j] > nums[i]$ ，则说明 $i$ 可以接在 $j$ 的后面形成一个下降的摆动序列，此时 $g[i] = \max(g[i], f[j] + 1)$ 。然后我们更新答案为 $\max(f[i], g[i])$ 。

最后，我们返回答案。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	complexity is O(n) due to a single pass through the array. Space complexity is O(1) using two variables for up and down states instead of full DP arrays, optimized from the naive O(n) DP solution.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checking if you correctly identify and track up and down states for DP transitions.
question_mark
Asking about handling consecutive equal numbers that do not contribute to wiggle subsequence.
question_mark
Expecting linear O(n) optimization using greedy updates rather than full DP arrays.

warning

常见陷阱

外企场景

error
Treating consecutive equal numbers as valid wiggle differences.
error
Overcomplicating DP with full arrays instead of maintaining just up/down states.
error
Failing to handle edge cases where array length is 1 or 2.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual longest wiggle subsequence instead of just its length.
arrow_right_alt
Count the number of distinct wiggle subsequences of maximal length.
arrow_right_alt
Adapt the problem to allow zero differences as valid for subsequence formation.

help

常见问题

外企场景

继续练习

#410 分割数组的最大值 #435 无重叠区间 #122 买卖股票的最佳时机 II