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