image.png
    在分析题目之前，先解释几个名词。
    上升摆动序列：某个序列被称为「上升摆动序列」，当且仅当该序列是摆动序列，且最后一个元素呈上升趋势。如序列 [1,3,2,4] 即为「上升摆动序列」。
    下降摆动序列：某个序列被称为「下降摆动序列」，当且仅当该序列是摆动序列，且最后一个元素呈下降趋势。如序列 [4,2,3,1] 即为「下降摆动序列」。

    状态定义：up[i]：前i个数字的最长上升摆动序列的长度，down[i]：前i个数字的最长下降摆动序列的长度。
    状态转移：考虑nums[i] 与 nums[i - 1]，有以下三种情况：

    • nums[i] == nums[i- 1]

    此时不会对摆动序列的长度照成任何影响，我们只需要把状态往后传递即可。

    • nums[i] > nums[i - 1]

    对于上升摆动序列而言，其状态来源于up[i-1]和down[i-1]，即up[i]=max(up[i-1], down[i-1]+1)
    对于下降摆动序列而言，其长度不会发生改变，只需要把状态往后传递，即down[i]=down[i-1]

    • nums[i] < nums[i-1]

    对于上升摆动序列而言，其长度不会发生改变，只需要把状态往后传递，即up[i]=up[i-1]。
    对于下降摆动序列而言，其状态来源于up[i-1]和down[i-1]，即down[i]=max(up[i-1]+1, down[i-1])

    • 时间复杂度：O(n)

    • 空间复杂度：O(n)

      1. class Solution {
      2.   public int wiggleMaxLength(int[] nums) {
      3.       int n = nums.length;
      4.       if(n < 2){
      5.           return n;
      6.       }
      7.       int[] up = new int[n]; //上升摆动序列
      8.       int[] down = new int[n]; //下降摆动序列
      10.       up[0] = down[0] = 1;
      12.       for(int i = 1; i < n; i++){
      13.           if(nums[i] > nums[i-1]){
      14.               up[i] = Math.max(up[i-1], down[i-1] + 1);
      15.               down[i] = down[i-1];
      16.           }else if(nums[i] < nums[i-1]){
      17.               up[i] = up[i-1];
      18.               down[i] = Math.max(down[i-1], up[i-1] + 1);
      19.           }else{
      20.               up[i] = up[i-1];
      21.               down[i] = down[i-1];
      22.           }
      23.       }
      24.       return Math.max(down[n-1], up[n-1]);
      25.   }
      26. }