LeetCode #376：Wiggle Subsequence(摆动序列)

题目描述

摆动序列的定义为：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列，规定少于等于两个元素的序列也是摆动序列。下面尝试使用贪心和动态规划两种思想来解题。

贪心

若我们把数组的下标为 x 轴、值为 y 轴，在一个二维坐标系中描点连线画出 “函数” 图像，我们可以总是选择该 “函数” 的 “极值点” 作为摆动序列的一部分，就能使得该序列尽可能长（证明方法见力扣官方题解）。注意序列两端的元素也是符合题意的。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return n;

        int count = 1; // 最终结果初始化为1，因为默认最右边有一个极值
        int curSub = 0; // 当前数与前一个数的差
        int preSub = 0; // 前一个数与再前一个数的差

        for(int i = 1; i < n; i ++) {
            curSub = nums[i] - nums[i - 1];

            if((curSub > 0 && preSub <= 0) || (curSub < 0 && preSub >= 0)) { // curSub与preSub异号时碰到极值，其中preSub >= 0的等于号是对最左边可能的极值和诸如0,0,1序列的特殊处理
                count ++;
                preSub = curSub; // preSub仅在遇到极值时更新（斜率符号改变）
            }
        }

        return count;
    }
};

动态规划

设 dp 状态 dp[0][i]，表示前 i 个数中以 nums[i] 结尾的最长上升摆动序列长度；设 dp 状态 dp[1][i]，表示前 i 个数中以 nums[i] 结尾的最长下降摆动序列长度。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return n;

        vector<vector<int>> dp(2, vector<int>(n, 1));
        dp[0][0] = 1;
        dp[1][0] = 1;
        for(int i = 1; i < n; i ++) {
            for(int j = 0; j < i; j ++) {
                if(nums[i] > nums[j]) { // 将nums[i]尝试接到前面某个极小值后面，作为极大值
                    dp[0][i] = max(dp[0][i], dp[1][j] + 1);
                }

                if(nums[i] < nums[j]) { // 将nums[i]尝试接到前面某个极大值后面，作为极小值
                    dp[1][i] = max(dp[1][i], dp[0][j] + 1);
                }
            }
        }

        return max(dp[0][n - 1], dp[1][n - 1]);
    }

};

当然我们还可以设 dp 状态 dp[0][i]，表示数组 nums 的子数组 nums[0…i] 的最长上升摆动序列长度；设 dp 状态 dp[1][i]，表示数组 nums 的子数组 nums[0…i] 的最长下降摆动序列长度（注意区分和上面状态定义的不同之处，这直接决定了算法的实现）。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return n;

        // 第0行表示子数组nums[0...i]的最长上升摆动序列长度，第1行表示子数组nums[0...i]的最长下降摆动序列长度
        vector<vector<int>> dp(2, vector<int>(n, 1));
        dp[0][0] = 1; 
        dp[1][0] = 1;
        for(int i = 1; i < n; i ++) {
            if(nums[i] > nums[i - 1]) { // 当前数大于前一个数时，即新的尾结点上升
                dp[0][i] = dp[1][i - 1] + 1; // 在前一个最长下降摆动序列基础上上升
                dp[1][i] = dp[1][i - 1]; // 当前数大于前一个数时，最长下降摆动序列长度与前一个数的最长下降摆动序列长度相同（即摆动序列末尾的数直接选前一个数一定能保证长度不变小）
            } else if(nums[i] < nums[i - 1]) { // 当前数小于前一个数时，即新的尾结点下降（逻辑同上）
                dp[0][i] = dp[0][i - 1];
                dp[1][i] = dp[0][i - 1] + 1;
            } else { // 当前数等于前一个数
                dp[0][i] = dp[0][i - 1];
                dp[1][i] = dp[1][i - 1];
            }
        }

        return max(dp[0][n - 1], dp[1][n - 1]);
    }
};