摆动序列

周子力大约 7 分钟教学文档贪心算法

题目描述

解题思路

我们要找的是数组 nums 中最长摆动子序列的长度。

摆动序列：相邻元素差值严格正负交替（不能为0）。
子序列不要求连续，但要保持原顺序。
例如：[1, 17, 5, 10, 13, 15, 10, 5, 16, 8] → 最长摆动子序列长度为 7。

✅ 核心观察：

摆动序列的本质是“方向交替”：上升 → 下降 → 上升 → ... 或下降 → 上升 → ...

因此，我们不需要构造子序列，只需统计方向发生有效切换的次数，再加上起始点，就是最长摆动子序列的长度。

💡 贪心策略：

从左到右扫描数组。
跳过所有“平缓”（curr_diff == 0）或“同方向延续”的部分。
只有当当前差值非零，且与上一个有效差值符号相反时，才认为出现了一个新的“摆动点”，计入长度。

📌 关键变量解释：

prev_diff：记录上一个有效的非零差值（即上一次真正构成“上升”或“下降”的差值）。
- 初始为 0，表示尚未确定初始方向。
count：摆动序列长度，初始为 1（至少包含第一个元素）。

🔁 三、代码逻辑详解

def wiggleMaxLength(nums):
    """
    返回最长摆动子序列的长度。
    贪心策略：只在方向发生改变时计数（跳过中间平缓或同向点）。
    """
    n = len(nums)
    if n <= 1:
        return n

    # 用 prev_diff 记录上一个有效的差值（非零）
    prev_diff = 0
    count = 1  # 至少包含第一个元素

    for i in range(1, n):
        curr_diff = nums[i] - nums[i - 1]
        # 只有当 curr_diff 非零，且与 prev_diff 符号相反时，才构成摆动
        if curr_diff != 0 and (prev_diff == 0 or curr_diff * prev_diff < 0):
            count += 1
            prev_diff = curr_diff

    return count

条件分解：

条件1：`curr_diff != 0`

排除相等元素（差为0），因为摆动序列不允许平台或平缓段。

条件2：`prev_diff == 0 or curr_diff * prev_diff < 0`

prev_diff == 0：这是第一个非零差值，无论正负，都算作有效起点（比如 [1, 7, ...]，+6 是第一个摆动）。
curr_diff * prev_diff < 0：说明当前差值与上一个有效差值符号相反，即方向发生了切换（上升→下降或下降→上升），构成一次“摆动”。

✅ 只要满足这两个条件，就说明我们遇到了一个新的“转折点”，应当将其纳入摆动子序列。

注意：我们并不真的“删除”中间元素，而是通过跳过同向或平缓段，隐式地构建了最长摆动子序列。

🌰 四、举例说明

示例：`nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]`

差值序列（原始）：

+16, -12, +5, +3, +2, -5, -5, +11, -8

我们只保留方向变化点：

+16 → 第一个有效差，count=2
-12 → 与 +16 反向，count=3
+5 → 与 -12 反向，count=4
+3, +2 → 同向（仍为上升），跳过
-5 → 与 +5 反向，count=5
-5 → 同向（仍为下降），跳过
+11 → 反向，count=6
-8 → 反向，count=7

✅ 最终 count = 7，正确！

注意：虽然原始序列有 10 个数，但我们只在方向切换处计数，自动跳过了 [10,13,15] 这样的上升平台中的中间点。

✅ 五、为什么这是贪心且正确的？

贪心选择：每次遇到方向反转，就立刻“采纳”当前点作为摆动点。
最优子结构：局部采纳转折点不会影响后续更优解，因为中间同向点对摆动无贡献。
正确性保证：
- 所有摆动序列必须包含这些方向转折点；
- 跳过同向点不会丢失更长的可能性；
- 因此，这种“只记录转折”的策略能得到理论最大长度。

⏱️ 六、复杂度分析

时间复杂度：O(n)，单次遍历。
空间复杂度：O(1)，仅用几个变量。

摆动序列问题：注意事项与启发

1. 贪心策略的理解

核心启发：这个问题的关键在于理解贪心策略：我们只需要关注序列中的“峰值”和“谷值”，而忽略单调递增或递减段中的中间元素。例如，在序列 [1, 2, 3, 2, 1] 中，我们只关心 1（谷）-> 3（峰）-> 1（谷）这三个点，中间的 2 和 2 可以被忽略。这样能保证我们得到最长的摆动子序列。
注意：这种贪心策略是正确的，因为它最大化了转折点的数量，而转折点的数量直接决定了摆动序列的长度。

2. 状态变量的设计

is_up 变量：用一个变量（如布尔值 is_up）来记录当前摆动序列的期望方向（上升或下降）是解决这个问题的核心。它帮助我们判断当前的差值 diff 是否形成了一个有效的“转折”。
max_length 变量：它记录了到目前为止找到的最长摆动序列的长度。
注意：初始状态 is_up 设为 None 是一个很好的设计，它表示我们还没有遇到第一个有效的非零差值，因此还没有确定初始方向。这避免了在开始时进行复杂的判断。

3. 处理相等元素

核心逻辑：当 diff == 0 时，意味着 nums[i] == nums[i-1]。这个元素必须被跳过，因为它不产生任何“摆动”。在代码中，使用 continue 语句可以优雅地跳过本次循环，处理下一个元素。
注意：不能简单地认为相等元素会重置序列，而是应该忽略它们，继续寻找下一个可能的转折点。

4. 差值符号的判断

关键判断：if diff > 0 != is_up: 是代码的核心逻辑。它的含义是：如果当前差值 diff 的符号（正或负）与上一个有效差值的符号 is_up 不同，那么就找到了一个转折点。
- diff > 0 会返回 True 或 False。
- != is_up 将这个布尔结果与 is_up (也是 True 或 False 或 None) 进行比较。
- 当 is_up 为 None 时，任何 True/False 都不等于 None，所以第一个非零差值总是能触发 max_length 的增加。
注意：这种写法简洁地处理了初始状态和方向改变两种情况。

5. 边界条件

单元素/两元素：当 n <= 1 时，直接返回 n。单个元素本身就是长度为 1 的摆动序列。两个不等元素构成长度为 2 的摆动序列。
全相等序列：如 [7, 7, 7]，所有差值都为 0，max_length 保持初始值 1。
单调序列：如 [1, 2, 3, 4]，只有第一个差值 1->2 有效，max_length 增加到 2，后续差值都与 is_up (True) 相同，因此不再增加。最终长度为 2。

6. 启发

贪心 vs 动态规划：这个问题可以用动态规划解决（维护以每个位置结尾的最长上升摆动子序列和最长下降摆动子序列），但贪心解法更简洁高效（ $O(N)$ 时间， $O(1)$ 空间）。这启发我们，对于某些最优化问题，寻找一个巧妙的贪心策略可能比复杂的 DP 更优。
状态机思想：is_up 变量的使用体现了一种简单的“状态机”思想。我们根据当前状态（is_up）和输入（diff）来决定如何更新状态和结果。这是解决许多序列问题的有力工具。
问题转化：将寻找“摆动子序列”转化为寻找“转折点”的数量，是一种有效的思路转化。将复杂问题简化为其本质特征，是算法设计中常用的技巧。
一次遍历：该算法只需要一次遍历就能解决问题，体现了高效算法设计的精髓。在设计算法时，应思考是否可以通过一次遍历完成任务。