Medium

题目描述

摆动序列 是一个数列，其中连续数字之间的差值严格在正数和负数之间交替。第一个差值（如果存在）可以是正数或负数。只有一个元素的序列和有两个不相等元素的序列都被认为是摆动序列。

  • 例如，[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
解释：有几个子序列都可以达到这个长度。
其中一个是 [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. 维护当前的趋势方向（上升或下降）
  2. 当趋势发生改变时，计数器加1，并更新趋势方向
  3. 相等的连续元素不影响摆动序列的长度

动态规划思路

定义状态：

  • up[i]：以第i个元素结尾，且最后一段是上升的最长摆动序列长度
  • down[i]：以第i个元素结尾，且最后一段是下降的最长摆动序列长度

状态转移：

  • 如果 nums[i] > nums[i-1]：up[i] = down[i-1] + 1, down[i] = down[i-1]
  • 如果 nums[i] < nums[i-1]：down[i] = up[i-1] + 1, up[i] = up[i-1]
  • 如果 nums[i] == nums[i-1]：up[i] = up[i-1], down[i] = down[i-1]

贪心算法时间复杂度O(n)，空间复杂度O(1)，是最优解法。

代码实现

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;
        
        int prevDiff = 0, currDiff = 0;
        int result = 1;  // 至少包含第一个元素
        
        for (int i = 1; i < n; i++) {
            currDiff = nums[i] - nums[i-1];
            // 当前差值与前一个差值符号不同，或者是第一个非零差值
            if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
                result++;
                prevDiff = currDiff;
            }
        }
        
        return result;
    }
};

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        
        prev_diff = 0
        result = 1  # 至少包含第一个元素
        
        for i in range(1, n):
            curr_diff = nums[i] - nums[i-1]
            # 当前差值与前一个差值符号不同，或者是第一个非零差值
            if (curr_diff > 0 and prev_diff <= 0) or (curr_diff < 0 and prev_diff >= 0):
                result += 1
                prev_diff = curr_diff
        
        return result

public class Solution {
    public int WiggleMaxLength(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return n;
        
        int prevDiff = 0, currDiff = 0;
        int result = 1;  // 至少包含第一个元素
        
        for (int i = 1; i < n; i++) {
            currDiff = nums[i] - nums[i-1];
            // 当前差值与前一个差值符号不同，或者是第一个非零差值
            if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
                result++;
                prevDiff = currDiff;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function(nums) {
    const n = nums.length;
    if (n <= 1) return n;
    
    let prevDiff = 0, currDiff = 0;
    let result = 1;  // 至少包含第一个元素
    
    for (let i = 1; i < n; i++) {
        currDiff = nums[i] - nums[i-1];
        // 当前差值与前一个差值符号不同，或者是第一个非零差值
        if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
            result++;
            prevDiff = currDiff;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
贪心算法O(n)O(1)
动态规划O(n)O(1)

推荐使用贪心算法，代码简洁且效率最高。

相关题目