最长摆动子序列（Wiggle Subsequence）

题目描述
给定一个整数数组 nums，如果连续数字之间的差值严格地交替变化：正、负、正、负……（或负、正、负、正……），则称为“摆动序列”。子序列可以通过从原始序列中删除一些元素（或不删除）得到。求 nums 的最长摆动子序列的长度。

示例

输入: nums = [1,7,4,9,2,5]
输出: 6
说明: 整个序列就是一个摆动序列：[1,7,4,9,2,5] 的差值依次是 (6,-3,5,-7,3)，交替变化。

输入: nums = [1,17,5,10,13,15,10,5,16,8]
输出: 7
说明: 最长摆动子序列可以是 [1,17,5,10,5,16,8]，差值序列 (16,-12,5,-5,11,-8)。

输入: nums = [1,2,3,4,5,6,7,8,9]
输出: 2
说明: 最长摆动子序列可能是 [1,2]，长度仅为 2。

解题过程

1. 问题理解

摆动序列的定义是：序列中相邻元素的差值 nums[i] - nums[i-1] 正负交替。
我们要求的是：不改变元素顺序，但可以删除某些元素，使剩下的序列满足摆动条件，且长度最长。

关键点：

• 子序列不一定连续。
• 摆动是指差值符号交替变化，差值不能为 0（即相等的数相邻会破坏摆动）。
• 如果序列中有连续相等的数，我们可以只保留其中一个，因为相邻相等不会产生符号变化。

2. 初步思路

我们可以用一个简单的贪心思路，但这里我们先从动态规划入手，因为动态规划更容易系统化理解，也能处理更复杂的问题变种。

定义状态：
设：

• up[i]：以 nums[i] 结尾，且最后一个差值为正（即 nums[i] > nums[某个前面的数]）的最长摆动子序列长度。
• down[i]：以 nums[i] 结尾，且最后一个差值为负（即 nums[i] < nums[某个前面的数]）的最长摆动子序列长度。

注意：这里“最后一个差值”是指子序列中最后两个元素的差值，而不是和原序列中的前一个元素比较。

3. 状态转移方程

我们考虑从 j = 0 到 i-1 的所有可能的前一个元素 nums[j]，但这样复杂度是 O(n²)。
但我们可以优化到 O(n)：我们不需要枚举所有 j，只需要在遍历时维护 up[i] 和 down[i] 即可。

优化方法：
遍历数组，对于每个 nums[i]，比较它和 nums[i-1]：

1. 如果 nums[i] > nums[i-1]：
   • 要形成以 nums[i] 结尾、最后差值为正的摆动子序列，可以在 nums[i-1] 结尾且最后差值为负的子序列后面加上 nums[i]，长度是 down[i-1] + 1。
     同时，up[i-1] 可能保持不变（因为不能连续两个上升差值）。
   • 所以：

\[ up[i] = \max(up[i-1],\ down[i-1] + 1) \]

\[ down[i] = down[i-1] \quad \text{（因为当前是上升，不会影响以下降结尾的长度）} \]

 实际上，`down[i]` 可以保持不变，因为 `nums[i]` 不会让下降序列长度增加（这里需要仔细思考）。

2. 如果 nums[i] < nums[i-1]：
   • 要形成以 nums[i] 结尾、最后差值为负的摆动子序列，可以在 nums[i-1] 结尾且最后差值为正的子序列后面加上 nums[i]，长度是 up[i-1] + 1。
   • 所以：

\[ down[i] = \max(down[i-1],\ up[i-1] + 1) \]

\[ up[i] = up[i-1] \]

3. 如果 nums[i] == nums[i-1]：
   • 当前元素不能改变摆动方向，所以 up[i] = up[i-1]，down[i] = down[i-1]。

更清晰的推导：
我们定义：

• up[i]：考虑前 i+1 个元素，且最后一步是上升（即最后两个元素是上升关系）的最长摆动子序列长度。
• down[i]：考虑前 i+1 个元素，且最后一步是下降的最长摆动子序列长度。

初始化：

• 对于单个元素，它既可以看作是上升序列的开始，也可以看作是下降序列的开始，长度都是 1。
  所以 up[0] = 1, down[0] = 1。

转移（i 从 1 到 n-1）：

• 如果 nums[i] > nums[i-1]：
  上升序列可以由前面的下降序列转移而来：up[i] = down[i-1] + 1。
  下降序列保持不变：down[i] = down[i-1]。
• 如果 nums[i] < nums[i-1]：
  下降序列可以由前面的上升序列转移而来：down[i] = up[i-1] + 1。
  上升序列保持不变：up[i] = up[i-1]。
• 如果相等：
  up[i] = up[i-1], down[i] = down[i-1]。

最终答案是 max(up[n-1], down[n-1])。

4. 举例推导

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

我们按正确逻辑重算：

初始化：
up[0]=1, down[0]=1

i=1, nums[1]=7 > nums[0]=1：

• up[1] = down[0] + 1 = 2
• down[1] = down[0] = 1

i=2, nums[2]=4 < nums[1]=7：

• down[2] = up[1] + 1 = 2 + 1 = 3
• up[2] = up[1] = 2

i=3, nums[3]=9 > nums[2]=4：

• up[3] = down[2] + 1 = 3 + 1 = 4
• down[3] = down[2] = 3

i=4, nums[4]=2 < nums[3]=9：

• down[4] = up[3] + 1 = 4 + 1 = 5
• up[4] = up[3] = 4

i=5, nums[5]=5 > nums[4]=2：

• up[5] = down[4] + 1 = 5 + 1 = 6
• down[5] = down[4] = 5

最终 max(6,5)=6 ✅

5. 空间优化

由于 up[i] 和 down[i] 只依赖于前一个状态，所以可以用两个变量 up 和 down 来替代数组，空间 O(1)。

伪代码：

up = 1, down = 1
for i from 1 to n-1:
    if nums[i] > nums[i-1]:
        up = down + 1
    else if nums[i] < nums[i-1]:
        down = up + 1
    # 相等时不更新
return max(up, down)

注意：当 nums[i] > nums[i-1] 时，up 要用旧的 down 更新，所以需要临时变量保存旧值吗？
实际上，这里 up 和 down 的更新是交替的，不会同时用旧值更新两个变量。我们可以直接写，因为：

• 当上升时，新的 up 依赖于旧的 down，而旧的 down 没有被改变，所以可以直接用。
• 当下降时类似。

6. 为什么贪心有效

动态规划本质上就是贪心思路的体现：
我们只需要考虑相邻元素的大小关系，如果差值符号交替变化，就增加长度；否则保持长度不变。
换句话说，最长摆动子序列的长度就是序列中“峰”和“谷”的数量 + 1（首尾各算一个点）。

等价贪心算法：
遍历数组，统计符号变化的次数，遇到相等数时跳过。
初始长度 = 1，从 i=1 开始，记录前一个差值符号 prevDiff，当前差值符号 curDiff。
如果 curDiff 与 prevDiff 符号相反，则长度+1，并更新 prevDiff = curDiff。
但这样实现稍繁琐，不如直接用上述动态规划。

7. 最终代码（Python）

def wiggleMaxLength(nums):
    n = len(nums)
    if n < 2:
        return n
    up = down = 1
    for i in range(1, n):
        if nums[i] > nums[i-1]:
            up = down + 1
        elif nums[i] < nums[i-1]:
            down = up + 1
    return max(up, down)

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

小结
本题是经典的线性动态规划问题，关键在于定义两个状态表示最后一步是上升或下降的最长子序列长度，通过相邻元素比较进行转移，最终得到最优解。这种方法也适用于更复杂的变种，比如允许差值等于0的情况（需调整定义）或带权值的最长摆动子序列。