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)``。