0376. Wiggle Subsequence ======================== 题目信息 -------- :题号: 0376 :难度: Medium :主题: 子序列、相邻差值、严格正负交替、最大长度 :原题: `LeetCode 0376 `_ :重点: 子序列保持原下标顺序但可以跳过元素、相邻差不能为零、首个非零差可以为正或负 题目重述 -------- 如果一个序列中相邻元素之差严格按照正、负、正、负或负、正、负、正的形式交替,则该序列称为摆动序列。只有一个元素的序列,以及任意两个不相等元素组成的序列,也符合定义。 给定整数数组 ``nums``,返回其中最长摆动子序列的长度。子序列可以删除原数组中的若干元素,但保留下来的元素必须维持原有下标顺序;相等元素之间的差为零,不能形成一次有效摆动。数组长度位于 ``[1, 1000]``,元素位于 ``[0, 1000]``。 自建示例 -------- 重复值不能形成摆动: .. code-block:: text 输入:nums = [3,3,2,5,4] 输出:4 解释:可以选择 [3,2,5,4],相邻差依次为负、正、负;两个连续的 3 不能同时用于严格摆动。 单调数组: .. code-block:: text 输入:nums = [1,2,3,4] 输出:2 解释:任取两个递增元素可以组成长度为 2 的摆动序列,但加入第三个元素后两个差值同为正,无法继续交替。 只记录最后一次差值的方向 -------------------------- 令 ``up`` 为处理到当前位置、最后一个有效差值为正的最长摆动子序列长度,``down`` 同理表示最后差值为负。若当前值比前一个值大,可以把它接在某个 ``down`` 状态后,更新 ``up = down + 1``;若更小,则更新 ``down = up + 1``;相等时不产生有效方向,两个状态都不变。 这里使用相邻原数组元素完成转移并不会限制子序列:当当前值提供同一方向的更好末尾时,它可以替换旧末尾而不减少后续形成相反差值的机会。因而两个状态已经压缩了所有需要的信息。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int wiggleMaxLength(std::vector& nums) { int up = 1; int down = 1; for (int i = 1; i < static_cast(nums.size()); ++i) { if (nums[i] > nums[i - 1]) { up = down + 1; } else if (nums[i] < nums[i - 1]) { down = up + 1; } } return std::max(up, down); } }; 代码分析 -------- ``up`` 与 ``down`` 始终代表两种可能的末尾方向,首个非零差值可任选方向;相等值不会错误地增加长度。每个元素只进行一次比较,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。