1. 问题背景与理解

第一次看到LeetCode 376题"摆动序列"这个标题时，我脑海中浮现的是一条波浪形的曲线。这道题在动态规划分类中属于中等难度，但实际解题时需要跳出常规思维模式。题目要求我们找出数组中最长的摆动子序列长度，所谓摆动序列就是相邻元素的差值正负交替出现。

举个例子，对于数组[1,7,4,9,2,5]，最长的摆动序列就是整个数组本身，因为相邻元素的差值序列是(6,-3,5,-7,3)，正负交替出现。而像[1,4,7,2,5]这样的数组，最长摆动序列是[1,4,2,5]或者[1,7,2,5]，长度都是4。

2. 解题思路分析

2.1 暴力解法与复杂度分析

最直观的解法是枚举所有可能的子序列，然后检查每个子序列是否是摆动序列。对于一个长度为n的数组，子序列的数量是2^n，因此这种解法的时间复杂度是O(2^n)，显然无法处理较大规模的输入。

2.2 动态规划解法

更高效的解法是使用动态规划。我们可以定义两个状态数组：

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

状态转移方程如下：

• 如果nums[i] > nums[j]，则up[i] = max(up[i], down[j] + 1)
• 如果nums[i] < nums[j]，则down[i] = max(down[i], up[j] + 1)

这种解法的时间复杂度是O(n^2)，空间复杂度是O(n)。

2.3 优化解法

实际上，我们可以将空间复杂度优化到O(1)。只需要维护两个变量：

• up：当前上升摆动序列的最大长度
• down：当前下降摆动序列的最大长度

遍历数组时：

• 如果nums[i] > nums[i-1]，说明当前是上升趋势，up = down + 1
• 如果nums[i] < nums[i-1]，说明当前是下降趋势，down = up + 1

这种优化解法的时间复杂度是O(n)，空间复杂度是O(1)。

3. 代码实现与解析

3.1 C++实现

class Solution { public: int wiggleMaxLength(vector<int>& nums) { if (nums.size() < 2) return nums.size(); int up = 1, down = 1; for (int i = 1; i < nums.size(); i++) { if (nums[i] > nums[i-1]) { up = down + 1; } else if (nums[i] < nums[i-1]) { down = up + 1; } } return max(up, down); } };

3.2 Python实现

def wiggleMaxLength(nums): if len(nums) < 2: return len(nums) up = down = 1 for i in range(1, len(nums)): if nums[i] > nums[i-1]: up = down + 1 elif nums[i] < nums[i-1]: down = up + 1 return max(up, down)

3.3 Java实现

class Solution { public int wiggleMaxLength(int[] nums) { if (nums.length < 2) return nums.length; int up = 1, down = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i-1]) { up = down + 1; } else if (nums[i] < nums[i-1]) { down = up + 1; } } return Math.max(up, down); } }

4. 边界条件与特殊情况处理

4.1 空数组或单元素数组

对于空数组，应该返回0；对于只有一个元素的数组，摆动序列长度自然是1。这是最基础的边界条件。

4.2 连续相等元素

当数组中存在连续相等的元素时，这些元素不会影响摆动序列的长度。例如[1,1,1,2,2,3,3,3,4]的最长摆动序列长度与[1,2,3,4]相同。

4.3 单调递增或递减数组

对于严格单调递增的数组如[1,2,3,4,5]，最长摆动序列长度是2（可以选第一个和第二个元素）；同样，严格单调递减的数组也是如此。

5. 算法复杂度分析

5.1 时间复杂度

优化后的解法只需要一次遍历数组，因此时间复杂度是O(n)，其中n是数组的长度。

5.2 空间复杂度

我们只使用了常数个额外变量（up和down），因此空间复杂度是O(1)。

6. 实际应用场景

摆动序列的概念在实际中有多种应用：

1. 股票价格分析：寻找价格波动较大的时期
2. 信号处理：识别信号中的波动模式
3. 路径规划：寻找交替上升下降的路径
4. 数据压缩：用摆动序列表示数据的变化趋势

7. 常见错误与调试技巧

7.1 忽略连续相等元素

很多初学者会错误地认为连续相等的元素会中断摆动序列。实际上，它们应该被跳过，不影响摆动序列的判断。

7.2 初始化错误

up和down的初始值应该都是1，因为单个元素本身就是长度为1的摆动序列。有些同学会错误地初始化为0。

7.3 比较符号错误

在比较当前元素和前一个元素时，容易混淆大于和小于符号。建议在写代码时添加明确的注释。

8. 算法优化思路

虽然我们已经将算法优化到O(n)时间复杂度和O(1)空间复杂度，但还可以考虑以下优化：

1. 提前终止：如果在遍历过程中发现up或down已经达到数组长度，可以提前结束循环
2. 并行计算：对于超大数组，可以考虑将数组分割后并行计算
3. 增量处理：对于流式数据，可以设计增量算法实时更新摆动序列长度

9. 相关题目推荐

为了加深对摆动序列问题的理解，建议练习以下LeetCode题目：

• 300. 最长递增子序列
• 673. 最长递增子序列的个数
• 334. 递增的三元子序列
• 646. 最长数对链

10. 个人解题心得

在实际解决这个问题时，我最初尝试了动态规划的二维解法，虽然正确但不够高效。后来通过观察发现只需要维护两个状态变量即可，大大简化了代码。这让我意识到，有时候问题的优化方向不一定是更复杂的算法，而是寻找更简洁的状态表示方式。

另一个收获是理解到摆动序列的本质是寻找序列中的"转折点" - 即从上升到下降或从下降到上升的转折位置。这种理解帮助我在解决类似问题时能够更快地抓住关键。