Shouyu

Appearance

摆动序列 ​

题目描述 ​

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

题目链接：https://leetcode.cn/problems/wiggle-subsequence/

文章链接：https://programmercarl.com/0376.摆动序列.html

思考 ​

贪心解法 ​

摆动序列的关键是要找到峰值。

对于cur节点，设置prediff = nums[cur] - nums[cur-1] 和 curdiff = nums[cur+1] - nums[cur-1]。对于这个条件，判断一个峰值至少需要三个点。

题目还有例外，少于两个元素的序列也是摆动序列。我们可以认为 [1] [1,2] 这样的摆动序列长度为1和2。

对于长度少于1，直接返回1.长度大于一的，我们从i = 1开始遍历，假设i=1这个点左边有一个prediff，然后置遍历到nums.size()-1，最后一个元素不遍历，不再判断是否为峰值，而是直接断定其是一个峰值，这就要求我们从result = 1开始计数。

那么对于prediff和curdiff满足什么条件的时候算一个峰值呢？

最基本的肯定是符号相反，一正一负。

还有其他情况，

情况一：上下坡中有平坡，比如：

img

这个摆动序列长度显然是3，那么峰值究竟是哪几个点？其实就是两个1和1个2，哪个2？其实要不就是最左边的2，要不就是最右边的2.我们可以统一规则，最右边的2是一个峰值，那么应该满足：

(preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)

情况二：首尾两端

第一个点为什么是计算为峰值？我们假设对于第一个值他的prediff为0，这样就满足preDiff <= 0 && curDiff > 0，对于最后一个值自动视为峰值，所以result从1开始累计。

情况三：单调坡中有平坡

img

按照以上分析，会再三个地方记录峰值，但是实际上结果是2，我们认为单调坡中的平坡不能算峰值。怎么解决？

原来

i = 0、1、2、3、4

prediff = 0、1、0、0、1

curdiff = 1、0、0、1、1

需要变为

i = 0、1、2、3、4

prediff = 0、1、1、1、1

curdiff = 1、0、0、1、1

我们需要遇到峰值时才更新prediff，让prediff = curdiff，这样prediff再单调平坡的时候不会变化。

动态规划思路 ​

定义

C++
// dp[i][0]: 以第i个元素结尾，且第i-1到第i是上升的最长摆动序列长度
// dp[i][1]: 以第i个元素结尾，且第i-1到第i是下降的最长摆动序列长度

我们思考一个摆动序列的长度怎样增加？后面一个节点如何设置才能使当前摆动序列长度+1？

很简单，假设前面一个元素是一个摆动序列的末尾，并且是在上升，如[1,5,3,7]，这时我们在后面只能添加比7小的数才能确定为这个已有的摆动序列长度+1，同理，如果前面元素是摆动序列的末尾，且在下降，那么我们添加一个大元素可使长度+1。

基于以上推断，我们就很好理解dp数组含义了

dp[i][0]: 以第i个元素结尾，且第i-1到第i是上升的最长摆动序列长度

dp[i][1]: 以第i个元素结尾，且第i-1到第i是下降的最长摆动序列长度

为什么这么设置，因为我们也不知道当前元素的前一个元素是上升摆动序列的末尾还是下降摆动序列的末尾，我们只能假设这两种情况都可能出现。

递推公式：

对于第i个元素，若它比前一个元素大，那么它可以判定dp[i][0]的情况，可能是dp[i-1][1]+1或dp[i-2][1]+1或dp[i-3][1]+1.....我们不确定是哪一个，因此要确定之前的所有元素，以那个元素结尾的最长下降摆动序列长度。比如【1，5，3，7，6，5，4，9】，我们想确定dp【7】【0】，就得知道dp【6】【1】，显然dp【6】【1】、dp【5】【1】是一样得。这意味着，前一个元素得最大摆动序列长度在i=5时就已经出现了。

但我们不知道哪个之前的位置能给出最优解。必须尝试所有可能的转移。

对于第i个元素，若它比前一个元素小，同理。。。

优化 ​

动态规划的思想其实是状态转移得体现，我们抓住状态转移的本质：

一个大元素（比前一个元素大）会使下降序列+1，小元素会使上升序列+1，如果相等，则上升和下降序列长度均不变。

这里得上升下降序列指以前一个元素结尾的最长摆动序列

代码实现 ​

贪心

C++
#include <vector>
using namespace std;

int wiggleMaxLength(vector<int> &nums) {
    if (nums.size() <= 1)
        return nums.size();
    int prediff = 0;
    int curdiff = 0;
    int result = 1;
    for (int i = 0; i < nums.size() - 1; i++) {
        curdiff = nums[i + 1] - nums[i];
        if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)) {
            result++;
            prediff = curdiff;
        }
    }
    return result;
}

int main(){}

动态规划思路

C++
int wiggleMaxLengthDP(vector<int> &nums) {
    if (nums.size() < 2)
        return nums.size();

    // dp[i][0]: 以第i个元素结尾，且第i-1到第i是上升的最长摆动序列长度
    // dp[i][1]: 以第i个元素结尾，且第i-1到第i是下降的最长摆动序列长度
    vector<vector<int>> dp(nums.size(), vector<int>(2, 1));

    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                // 当前是上升，之前应该是下降
                dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            } else if (nums[i] < nums[j]) {
                // 当前是下降，之前应该是上升
                dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            }
        }
    }

    int result = 1;
    for (int i = 0; i < nums.size(); i++) {
        result = max(result, max(dp[i][0], dp[i][1]));
    }

    return result;
}

优化动态规划

C++
int wiggleMaxLengthDPOptimized(vector<int> &nums) {
    if (nums.size() < 2)
        return nums.size();

    // up: 当前位置结尾且最后一段上升的最长摆动序列长度
    // down: 当前位置结尾且最后一段下降的最长摆动序列长度
    int up = 1, down = 1;

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) {
            // 上升：可以在之前下降序列基础上+1
            up = down + 1;
        } else if (nums[i] < nums[i - 1]) {
            // 下降：可以在之前上升序列基础上+1
            down = up + 1;
        }
        // 如果相等，up和down都不变
    }

    return max(up, down);
}