376. 摆动序列

思路

首先，我们可以将摆动序列分为两种：

• 「上升摆动序列」，当且仅当该序列是摆动序列，且最后一个元素呈上升趋势。如序列 [1,3,2,4] 即为「上升摆动序列」。

• 「下降摆动序列」，当且仅当该序列是摆动序列，且最后一个元素呈下降趋势。如序列 [4,2,3,1] 即为「下降摆动序列」。

• 特别地，对于长度为1的序列，它既是「上升摆动序列」，也是「下降摆动序列」。

状态定义

当我们选择一个元素作为摆动序列的一部分时，它必然会与前一个元素构成上升趋势，或下降趋势。因此，我们可以定义两个数组 up[i] 和 down[i] ，分别表示到位置 i 的元素为止最长的 上升 / 下降 摆动序列的长度。

状态转移

假设 j < i ，那么 nums[i] 和 nums[j] 之间的大小关系存在三种情况：

• nums[i] > nums[j] ：说明 nums[j] 到 nums[i] 会形成上升趋势，所以到位置 i 的元素为止最长的 上升 摆动序列需要更新：到位置 j 的元素为止最长的 下降 摆动序列再加上 nums[i] ，即 up[i] = down[j] + 1;
• nums[i] < nums[j] ：说明 nums[j] 到 nums[i] 会形成下降趋势，所以到位置 i 的元素为止最长的 下降 摆动序列需要更新：到位置 j 的元素为止最长的 上升 摆动序列再加上 nums[i] ，即 down[i] = up[j] + 1;
• nums[i] = nums[j] ：说明 nums[j] 到 nums[i] 没有形成上升或下降的趋势，所以到位置 i 的元素为止最长的 上升/下降 摆动序列都不需要更新，即 down[i] = down[j]; up[i] = up[j];

初始化

根据题目可知，当只有一个元素时，默认它自己形成了摆动序列，长度为1，所以 up[0] = down[0] = 1; 。

最终的返回结果

由于最后一个元素可能形成上升摆动序列，也可能形成下降摆动序列，所以我们最终需要返回的是两种情况的最大值，即 max(up[n-1], down[n-1]);

代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> up(n), down(n);

        // 初始化
        up[0] = down[0] = 1;
        
        for(int i=1; i<n; ++i){
            for(int j=0; j<i; ++j){
                // 新的长度至少和之前保持一致
                down[i] = down[j];
                up[i] = up[j];
                if(nums[i] > nums[j]){
                    // 如果新加入的元素大于前一个元素
                    // 则可以在之前的下降子序列基础上变成上升子序列
                    up[i] = down[j] + 1;
                }
                else if(nums[i] < nums[j]){
                    // 如果新加入的元素小于前一个元素
                    // 则可以在之前的上升子序列基础上变成下降子序列
                    down[i] = up[j] + 1;
                }
            }
        }
        return max(up[n-1], down[n-1]);
    }
};

优化一：时间压缩

不难发现， 在遍历到 i 的时候，我们已经知道 i 之前的所有状态，所以只需要考虑 前一种状态即可，可以减少一个循环。

代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> up(n), down(n);

        // 初始化
        up[0] = down[0] = 1;
        
        for(int i=1; i<n; ++i){
            // 新的长度至少和之前保持一致
            down[i] = down[i-1];
            up[i] = up[i-1];
            if(nums[i] > nums[i-1]){
                // 如果新加入的元素大于前一个元素
                // 则可以在之前的下降子序列基础上变成上升子序列
                up[i] = down[i-1] + 1;
            }
            else if(nums[i] < nums[i-1]){
                // 如果新加入的元素小于前一个元素
                // 则可以在之前的上升子序列基础上变成下降子序列
                down[i] = up[i-1] + 1;
            }
        }
        return max(up[n-1], down[n-1]);
    }
};

优化二：空间压缩

再进一步，由于 up 和 down 都只和前一个状态有关，所以可以使用两个变量来保存。

代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        int up = 1, down = 1;
        
        for(int i=1; i<n; ++i){
            if(nums[i] > nums[i-1]){
                // 如果新加入的元素大于前一个元素
                // 则可以在之前的下降子序列基础上变成上升子序列
                up = down + 1;
            }
            else if(nums[i] < nums[i-1]){
                // 如果新加入的元素小于前一个元素
                // 则可以在之前的上升子序列基础上变成下降子序列
                down = up + 1;
            }
        }
        return max(up, down);
    }
};