题目

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

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

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

  1. 输入：nums = [1,7,4,9,2,5]
  2. 输出：6
  3. 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

  1. 输入：nums = [1,17,5,10,13,15,10,5,16,8]
  2. 输出：7
  3. 解释：这个序列包含几个长度为 7 摆动序列。
  4. 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

  1. 输入：nums = [1,2,3,4,5,6,7,8,9]
  2. 输出：2

提示：

  • 1 <= nums.length <= 1000

  • 0 <= nums[i] <= 1000


    进阶：你能否用 O(n) 时间复杂度完成此题?

    解题方法

    贪心算法

    局部最优：删除单调边中间的节点。
    全局最优：全局保留最多的峰值点。
    峰值点的判定条件如下：

    • cur = nums[i]-nums[i-1]
    • pre = nums[i-1]-nums[i-2]
    • (cur>0&&pre<=0) || (cur<0&&pre>=0)

时间复杂度O(n)，空间复杂度O(1)
C++代码：

  1. class Solution {
  2. public:
  3.     int wiggleMaxLength(vector<int>& nums) {
  4.         int n = nums.size();
  5.         if(n<=1)    return n;
  6.         int num = 1;
  7.         int cur = 0;
  8.         int pre = 0;
  9.         for(int i=1; i<n; i++) {
  10.             cur = nums[i]-nums[i-1];
  11.             if((cur>0&&pre<=0) || (cur<0&&pre>=0)) {
  12.                 num++;
  13.                 pre = cur;
  14.             }
  15.         }
  17.         return num;
  18.     }
  19. };

动态规划

对于一个下标i：

  • 使用top[i]表明以前i个元素中某一个为结尾的最长的上升摆动序列长度。
  • 使用down[i]表明以前i个元素中某一个为结尾的最长的下降摆动序列长度。

状态转移：
对于top[i]:

  1.   - 如果`nums[i]>nums[i-1]`，则`nums[i]`可以代替`nums[i-1]`成为新的上升摆动序列的结尾；或是跟在之前最长下降摆动序列的后面，构建新的上升摆动序列，此时`down[i-1]`代表前`i-1`个元素中最长的下降摆动序列，可以证明，`nums[i]`必然大于这个摆动序列的结尾。在两者中取最大值，即`top[i] = max(top[i-1], down[i-1]+1)`。
  2.   - 如果`nums[i]<=nums[i-1]`，那么总可以用`nums[i-1]`代替`nums[i]`以获得最长的上升摆动序列，因此`top[i]=top[i-1]`。

对于down[i]同理。
最终状态转移方程如下：
376. 摆动序列 - 图1
时间复杂度O(n)，空间复杂度O(n)
C++代码：

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

动态规划（优化）

从上述动态规划方法可以看出，程序只需要维护上一个top和down并推算出当前的top和down即可，无需使用数组。并且top和down的差值不会大于1，即max(top, down+1) = down+1。
时间复杂度O(n)，空间复杂度O(1)
C++代码：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int top = 1;
        int down = 1;

        for(int i=1; i<nums.size(); i++) {
            if(nums[i]>nums[i-1]) top = down+1;
            if(nums[i]<nums[i-1]) down = top+1;
        }
        return max(top, down);
    }
};