0376. Wiggle Subsequence

题目信息

题号:

0376

难度:

Medium

主题:

子序列、相邻差值、严格正负交替、最大长度

原题:

LeetCode 0376

重点:

子序列保持原下标顺序但可以跳过元素、相邻差不能为零、首个非零差可以为正或负

题目重述

如果一个序列中相邻元素之差严格按照正、负、正、负或负、正、负、正的形式交替,则该序列称为摆动序列。只有一个元素的序列,以及任意两个不相等元素组成的序列,也符合定义。

给定整数数组 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)。