LeetCode 376. 摆动序列

◎

本节目标

只保留趋势转折点，用两个长度状态在线性时间求最长摆动序列。

这是贪心综合中“删除无效中间状态”的必学母题。

题意与约束

从序列中选择一个子序列，使相邻差值正负交替；长度为一的序列也合法。求最大长度。

直接思路与瓶颈

枚举子序列有指数数量。动态规划可以记录以当前位置结尾的上升、下降长度，却没有利用到中间同向元素其实可被替换的事实。

贪心模型与算法推导

维护 up 与 down：遇到上升差值时令 up=down+1，遇到下降差值时令 down=up+1；相等差值不改变状态。本质是只保留每个趋势段最有利的端点。

正确性依据

同一上升段中，选择更大的末端永远不劣于更小末端，因为它更容易接上后续下降；下降段对称。于是内部同向元素可删除，仅在趋势翻转时增加一个元素。up 始终表示以正差结尾的最优长度，down 始终表示以负差结尾的最优长度，最终答案取两者最大值。

样例执行过程

[1,7,4,9,2,5] 的相邻方向依次为上、下、上、下、上，每次翻转都扩展答案，up/down 最终最大值为 6。[2,2,2] 没有严格方向，只保留一个元素。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

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

Python

Python 3

class Solution:
    def wiggleMaxLength(self, nums: list[int]) -> int:
        if not nums:
            return 0
        up = down = 1
        for index in range(1, len(nums)):
            if nums[index] > nums[index - 1]:
                up = down + 1
            elif nums[index] < nums[index - 1]:
                down = up + 1
        return max(up, down)

复杂度分析

时间 O(n)，仅维护两个状态，额外空间 O(1)。

边界与易错点

• 相邻相等不是摆动，不能增加长度。
• 空数组返回 0；非空常量序列返回 1。
• 这里的状态更新是贪心压缩后的 DP 形式，重点在端点支配关系。

模式迁移

当同一方向的中间选择不会改善后续可行性时，可压缩为趋势端点或少量状态，等待方向转折再扩展答案。