题链

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

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

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

示例 1:

  • 输入: [1,7,4,9,2,5]
  • 输出: 6
  • 解释: 整个序列均为摆动序列。

示例 2:

  • 输入: [1,17,5,10,13,15,10,5,16,8]
  • 输出: 7
  • 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:

  • 输入: [1,2,3,4,5,6,7,8,9]
  • 输出: 2

注意：输入序列中可能有相同的数字

贪心算法

思路：
首先，在尽可能取多元素的前提下，最优解必是全部选取
我们从头开始选取子列，若是连续两个差值同正负，在这三个元素当中，后两个元素必要是要舍弃一个的。这里假设差值都为正，那么如果我们期望选取下一个元素就能使下一差值为负的话，那么选取两个元素的较大者必然是更优的，也就是后者。所以，当两个连续差值同正负时，我们选择保留最后的元素。

当然这里要注意连续相同元素的出现，这里差值为零，非正也非负，需特殊对待。

初实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return 1;
    int start_idx = -1;
    for (int i = 1; i < n; i++) { //寻找第一个非零差值
        if (nums[i] != nums[i - 1]) {
            start_idx = i;
            break;
        }
    }
    if (start_idx == -1) return 1; //所有元素相同
    int pre = nums[start_idx], res = 2;
    bool increased = (nums[start_idx - 1] < nums[start_idx]); //上一组差值是否正
    for (int i = start_idx + 1; i < n; i++) {
        if (nums[i] == pre) continue;
        if (increased ^ (nums[i] > pre)) {
            res++;
            increased = !increased;
        }
        pre = nums[i];
    }
    return res;
}

感觉实现地略繁琐

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int wiggleMaxLength(vector<int>& nums) {
    if (nums.size() <= 1) return nums.size();
    int curDiff = 0; // 当前一对差值
    int preDiff = 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; // 注意这里，只在摆动变化的时候更新prediff
        }
    }
    return result;
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) {
        return n;
    }
    int up = 1, down = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1]) {
            up = max(up, down + 1);
        } else if (nums[i] < nums[i - 1]) {
            down = max(up + 1, down);
        }
    }
    return max(up, down);
}

思路：
这里的up和down是分别以正、负差值结束的最长子序列长度
现在从第一个元素开始，依次加入后面的元素。若加入元素与上一元素相等，那么无事发生；若大于上一元素，则旧的down序列(最长的以负差值结束的子列)添上新的元素则为一个(以正差值结束的子列)，则新的up即为max(up, down + 1)，新的down与旧down相等；小于的情况同理。

当然此处还能再优化
容易证明：同一序列的up与down的差值不会超过1
因此，max(up, down + 1)实际上与down + 1无异
另一个同理
优化后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) {
        return n;
    }
    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);
}