力扣376-摆动序列

一、原题题目

1.1 题目

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

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

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

1.2 示例

示例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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wiggle-subsequence

二、解题思路

2.1 动态规划（dp）思路解题

解题思路

在自己思考这个题目的时候就觉得这是一个动态规划的题目，但没能写出整体过程，参考官方题解。

当序列长度为 0 或 1 时，摆动序列的长度也对应为 0 或 1 。当序列长度 >=2 时，需要讨论。
遍历序列：up[i] 表示前 i 个数据并且最后是上升的最长摆动序列，称为最长上升摆动序列，down[i] 表示前 i 个数据并且最后是下降的最长摆动序列，称为最长下降摆动序列。

讨论当前第 i 个数的加入：

nums[i] = nums[i-1] ：摆动序列长度不变
nums[i] > nums[i-1] ：下降摆动序列不变

1.当 nums[i] 放入最长下降摆动序列 up[i] = down[i-1] + 1
2.当 nums[i] 放入最长上升摆动序列 up[i] = up[i-1]
nums[i] < nums[i-1] ：上升摆动序列不变

1.当 nums[i] 放入最长上升摆动序列 down[i] = up[i-1] + 1
2.当 nums[i] 放入最长下降摆动序列 down[i] = down[i-1]
详细代码（Java）

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;              // 记录数组的长度
        if (len<=1) return len;             // 如果数组不超过2个数，那么就是摆动序列
        int[] up = new int[len];            // 记录到每个位置的上升摆动序列长度
        int[] down = new int[len];          // 记录到每个位置的下降摆动序列长度
        up[0] = down[0] = 1;                // 第一个位置即可以看做是上升的或是下降的长度为1的摆动序列
        for (int i = 1;i<len;i++){      // 从第二个元素开始遍历
            if (nums[i]>nums[i-1]){     // 如果后一个元素比前一个大，则只会影响上升摆动序列长度
                up[i] = Math.max(up[i-1],down[i-1]+1);      // 只更新上升摆动序列长度
                down[i] = down[i-1];            // 下降序列长度不会影响
            }
            else if (nums[i]<nums[i-1]){    // 如果后一个元素比前一个小，则只会影响下降摆动序列长度，同上分析
                down[i] = Math.max(up[i-1]+1,down[i-1]);
                up[i] = up[i-1];
            }
            else {      // 如果后一个元素等于前值，则上升和下降都不影响
                up[i] = up[i-1];
                down[i] = down[i-1];
            }
        }
        return Math.max(up[len-1],down[len-1]);
    }
}

代码执行结果

观察到上述代码每次更新 up 和 down 数组时只用到了前一个值，并且最后返回结果也只用到最后的值，故在空间上还可以做一定的优化。

优化代码

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;          // 记录数组长度
        if (len<=1) return len;         // 如果数组不超过2个数，那么就是摆动序列
        int up = 1,down = 1;            // 刚开始第一个元素即是上升序列又是下降序列，且长度为1
        for (int i = 1;i<len;i++){      // 从第二个开始遍历
            if (nums[i]>nums[i-1]){     // 如果后一个元素比前一个大，只更新上升摆动序列长度
                up = Math.max(up,down+1);
            }
            else if (nums[i]<nums[i-1]){// 如果后一个元素比前一个小，只更新下降摆动序列长度
                down = Math.max(down,up+1);
            }
        }
        return Math.max(up,down);
    }
}

优化执行结果

空间复杂度上得到了一点提升，注意力扣每次跑代码测试用例可能有所差异，相同的代码每次跑结果可能都会有些差异。

2.2 贪心思路解题

解题思路

本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。那么当我么碰到连续上升或连续下降的数据时就要执行删除操作啦，那么问题就是留下哪一个数能使整个留下来的子序列为最长摆动序列。

局部最优： 当碰到单调坡度时，保留峰值即是局部最优的情况。
整体最优： 当整个序列有最多保留下来的峰值时，就是达到最长摆动序列的全局最优情况。

至于上述所说的为什么成立，这里借用网友题解的一张图尝试说明下原因，我个人觉得当我们碰到连续递增的序列时，例如 10，13，15 时，我们应该选择最大的保留，这样在后序数据中选择一个下降的数可接受范围更大，即可能使我们最终留下来的摆动序列最长。递减的序列同样道理应该选择最小的数保留。

详细代码（Java）

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;          // 记录数组长度
        if (len <= 1)   return len;     // 如果数组不超过2个数，那么就是摆动序列
        int curdiff = 0;                // 开始时的当前差值设为0
        int prediff = 0;                // 开始时的之前差值设为0
        int count = 1;                  // 刚开始第一个元素是峰值，统计1个
        for (int i = 1;i<len;i++){      // 从第二个开始遍历
            curdiff = nums[i] - nums[i-1];  // 计算当前差值
            // 如果当前差值与之前差值变号了，并且当前差值不是0则表示是峰值
            if (curdiff >0 && prediff<=0 || curdiff<0&&prediff>=0){
                count++;
                prediff = curdiff;
            }
        }
        return count;
    }
}