376. Wiggle Subsequence.md

376. Wiggle Subsequence

思路

给定一个数组，要求最长摆动子序列的长度。为了表述方便，我们将摆动数组分成两类:

1. 第一类，最后一个元素为较小值，例如243和3243这种；
2. 第二类，最后一个元素为较大值，例如24和324这种；

思路一

很明显应该应dp，我们可以定义两个状态数组dp0和dp1:

dp0[i]: 以nums[i]结束且为第一类的最大长度。
dp1[i]: 以nums[i]结束且为第二类的最大长度。

如何更新 dp0[i] 和 dp1[i]，我们可以从i往前看，根据nums[j]（j < i）与nums[i]的大小关系来更新dp0[i] 和 dp1[i]。

这种动归思路是最好想的，但是由于有两个循环，时间复杂度没有达到题目要求。

时间复杂度O(n^2), 空间复杂度O(n)。

思路二

同样用递归，同样定义两个状态数组dp0和dp1，只是此时状态定义与思路一不一样了:

dp0[i]: 直到nums[i]为止且为第一类的最大长度。
dp1[i]: 直到nums[i]为止且为第二类的最大长度。

那么如何更新 dp0[i] 和 dp1[i]呢？为了表述方便，先来定义两个量a和b：

1. 设直到nums[i-1]为止且为第一类的最长摆动数组的last元素（可能是nums[i-1]也可能不是）为a，则有a <= nums[i-1];
2. 设直到nums[i-1]为止且为第二类的最长摆动数组的last元素（可能是nums[i-1]也可能不是）为b，则有b >= nums[i-1];

现在再来看如何更新dp值， 有三种情况:

1. nums[i] == nums[i-1]，那么很明显dp0[i] = dp0[i-1]; dp1[i] = dp1[i-1];
2. nums[i] < nums[i-1]，则有nums[i] < nums[i-1] <= b，所以dp0[i] = dp1[i-1] + 1而dp1[i] = dp1[i-1];
3. nums[i] > nums[i-1]，则有nums[i] > nums[i-1] >= a，所以dp1[i] = dp0[i-1] + 1而dp0[i] = dp0[i-1];

所以我们只需要一遍遍历即可求解。

时间复杂度O(n)，空间复杂度O(n)，可用常用的滚动数组方法将空间复杂度优化至O(1)。

C++

思路一

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int>dp0(nums.size(), 1), dp1(nums.size(), 1);
        
        int res = 1;
        for(int i = 1; i < nums.size(); i++){
            int max_0 = 1, max_1 = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] < nums[j]) max_0 = max(max_0, 1 + dp1[j]);
                else if(nums[i] > nums[j]) max_1 = max(max_1, 1 + dp0[j]);
            }
            dp0[i] = max_0;
            dp1[i] = max_1;
            res = max(res, max(max_0, max_1));
        }
        return res;
    }
};

思路二

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int>dp0(nums.size(), 1), dp1(nums.size(), 1);
        
        for(int i = 1; i < nums.size(); i++){
            dp0[i] = dp0[i-1]; dp1[i] = dp1[i-1];
            if(nums[i] < nums[i-1]) dp0[i] = 1 + dp1[i-1];
            else if(nums[i] > nums[i-1]) dp1[i] = 1 + dp0[i-1];
        }
        return max(dp0.back(), dp1.back());
    }
};

思路二空间优化

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.empty()) return 0;
        int dp0 = 1, dp1 = 1;
        
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] < nums[i-1]) dp0 = 1 + dp1;
            else if(nums[i] > nums[i-1]) dp1 = 1 + dp0;
        }
        return max(dp0, dp1);
    }
};