LC376.摆动序列

题目描述

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。 给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。 示例 1： 输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。 示例 2： 输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。 示例 3： 输入：nums = [1,2,3,4,5,6,7,8,9] 输出：2 提示： 1 <= nums.length <= 1000 0 <= nums[i] <= 1000 进阶：你能否用 O(n) 时间复杂度完成此题?

题目解析

题目在说什么

这道题其实是在问：给你一串数字，你可以删掉一些数字，但不能改变剩下的数字顺序，最后让剩下的数字序列变成一个“上下上下”的波浪形状，就像山峰和山谷交替出现一样。我们要找的是这个波浪序列最长能有多长。

比如，数字序列 [1, 7, 4, 9, 2, 5] 本身就是上下交替的（1→7上升，7→4下降，4→9上升，9→2下降，2→5上升），所以最长长度就是6，也就是整个序列的长度。而 [1, 2, 3, 4, 5, 6, 7, 8, 9] 一直上升，没有上下交替，所以最长摆动序列只能是 [1, 9] 这样的两个数（一升一降其实只需要一次变化），长度是2。

注意：如果两个数字相等，比如 [1, 3, 3, 2]，中间的相等不会产生摆动，所以我们要忽略它们。

思路是怎么来的

想象你正在爬一座山，但这座山不是一直往上或一直往下，而是像过山车一样，一会儿上坡一会儿下坡。你要记录下你一共经历了多少次“上坡-下坡”的转折，这就是摆动序列的长度。

但是有一个关键点：如果你一直在上坡（比如 [1, 2, 3, 4]），其实你只算一次“上坡开始”和一次“下坡开始”（但这里没有下坡，所以只算开始的一次）。实际上，你只需要记住当前是在上坡还是下坡，然后一旦方向改变，就说明出现了一个“波峰”或“波谷”，这时候摆动序列就可以增加一个数字。

所以，我们只需要一次遍历，盯着当前的方向（上升还是下降），一旦方向变了，就记录一次。这就是贪心的思想：只保留那些让方向发生变化的点，忽略中间那些“顺路”的点。比如 [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]，我们只关心那些转折点：1→17（上升），17→5（下降），5→10（上升），10→15（上升，但这里没有转折，所以忽略15），15→10（下降，转折），10→5（下降，忽略5），5→16（上升，转折），16→8（下降，转折）。所以最终保留的序列是 [1, 17, 5, 10, 15, 10, 16, 8]，长度是7。

代码逐步拆解

我们来看参考代码，它用了一个叫“状态机”的方法，其实就是用三个状态来记录当前是“刚开始”、“正在上升”还是“正在下降”。

class Solution {
    public int wiggleMaxLength(int[] nums) {
        // 定义三个状态常量
        int beginState = 0;   // 初始状态
        int upState = 1;      // 上升状态
        int downState = 2;    // 下降状态

        // 如果数组长度小于2，直接返回长度（因为一个或两个不等元素也算摆动序列）
        if(nums.length < 2) {
            return nums.length;
        }

        int length = 1;       // 摆动序列至少包含第一个元素，所以长度初始为1
        int state = beginState; // 一开始处于初始状态

        // 从第二个元素开始遍历（下标1）
        for(int i = 1; i < nums.length; i++) {
            // 根据当前状态做不同处理
            if(state == beginState) {
                // 初始状态：比较当前元素和前一个元素
                if(nums[i] > nums[i-1]) {
                    // 如果上升，就进入上升状态，并且长度+1
                    state = upState;
                    length++;
                } else if(nums[i] < nums[i-1]) {
                    // 如果下降，就进入下降状态，并且长度+1
                    state = downState;
                    length++;
                }
                // 如果相等，什么都不做，状态不变
            } else if(state == upState) {
                // 当前处于上升状态：只有遇到下降时才说明出现波峰
                if(nums[i] < nums[i-1]) {
                    // 下降，说明趋势改变了，进入下降状态，长度+1
                    state = downState;
                    length++;
                }
                // 如果继续上升或相等，都不改变状态和长度