最长摆动子序列 题目描述： 给定一个整数数组 nums，返回 nums 中作为摆动序列的最长子序列的长度。摆动序列是指连续数字之间的差严格地在正数和负数之间交替。第一个差值（如果存在的话）可能是正数或负数。如果少于两个元素，则序列是摆动序列。例如，[ 1,7,4,9,2,5 ] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 正负交替。 解题过程： 问题分析： 我们需要找到最长的子序列（不要求连续），使得这个子序列中相邻元素的差值正负交替 关键观察：对于任意位置 i，它可能处于两种状态： up[ i]：以 i 结尾且最后一步是上升（nums[ i ] > 前一个元素）的最长摆动序列长度 down[ i]：以 i 结尾且最后一步是下降（nums[ i] < 前一个元素）的最长摆动序列长度 状态定义： up[ i ]：以第 i 个元素结尾，且最后一步是上升的最长摆动子序列长度 down[ i ]：以第 i 个元素结尾，且最后一步是下降的最长摆动子序列长度 状态转移方程： 对于每个位置 i，我们需要考虑所有 j < i 的情况： 如果 nums[ i] > nums[ j ]，那么 i 可以接在 j 的下降序列后面形成上升 up[ i] = max(up[ i], down[ j ] + 1) 如果 nums[ i] < nums[ j ]，那么 i 可以接在 j 的上升序列后面形成下降 down[ i] = max(down[ i], up[ j ] + 1) 初始化： 每个位置本身就是一个长度为1的摆动序列 up[ 0] = 1, down[ 0 ] = 1 优化实现： 实际上我们可以用 O(n) 时间复杂度的贪心解法： 维护两个变量 up 和 down，分别表示当前最长的上升摆动序列和下降摆动序列长度 遍历数组，当遇到上升时，up = down + 1 当遇到下降时，down = up + 1 具体步骤： 如果 nums.length < 2，直接返回数组长度 初始化 up = 1, down = 1 从 i = 1 开始遍历数组： 如果 nums[ i] > nums[ i-1 ]：up = down + 1 如果 nums[ i] < nums[ i-1 ]：down = up + 1 返回 max(up, down) 示例验证： 对于 nums = [ 1,7,4,9,2,5 ]： i=1: 1→7（上升），up = 1+1=2, down=1 i=2: 7→4（下降），down = 2+1=3, up=2 i=3: 4→9（上升），up = 3+1=4, down=3 i=4: 9→2（下降），down = 4+1=5, up=4 i=5: 2→5（上升），up = 5+1=6, down=5 最终结果为6，与题目示例一致。 这种解法的时间复杂度是 O(n)，空间复杂度是 O(1)，是最优解法。