1. 摆动序列问题概述摆动序列Wiggle Sequence是算法领域一个经典的数组处理问题题目编号376来源于LeetCode题库。这个问题要求我们找到一个数组中摆动最长的子序列长度。所谓摆动序列是指相邻元素的差值在正负之间严格交替变化的序列。举个例子对于数组 [1,7,4,9,2,5]其摆动序列可以是 [1,7,4,9,2,5]因为相邻元素的差值 (6,-3,5,-7,3) 正负交替出现。而 [1,4,7,2,5] 不是摆动序列因为 (3,3,-5,3) 的差值没有严格交替。2. 问题形式化定义与边界条件2.1 数学形式化定义给定一个整数数组 nums返回作为摆动序列的最长子序列的长度。摆动序列定义为对于所有 0 i len(subsequence)-1满足如果 subsequence[i] subsequence[i-1]那么 subsequence[i1] subsequence[i]或者如果 subsequence[i] subsequence[i-1]那么 subsequence[i1] subsequence[i]换句话说序列中相邻元素的差值必须严格正负交替。2.2 边界条件分析在实际编码实现时需要考虑以下边界情况空数组应该返回0单元素数组返回1单个元素视为摆动序列两元素数组如果两元素不等则返回2相等则返回1所有元素相等的数组只能返回1包含重复元素的数组需要正确处理连续相等的情况提示在实际面试中明确边界条件可以展示出思维的全面性这部分往往比写出核心算法更能体现编程素养。3. 贪心算法解决方案3.1 基本思路摆动序列问题可以使用贪心算法高效解决其核心思想是我们只需要统计序列中峰和谷的数量即可。具体来说初始化摆动序列长度为1至少包含第一个元素维护两个变量prevDiff前一对元素的差值和currDiff当前对元素的差值遍历数组当检测到摆动即prevDiff和currDiff符号相反时增加计数并更新prevDiff忽略那些不会改变摆动方向的中间元素这种方法的时间复杂度是O(n)空间复杂度是O(1)是最优解。3.2 代码实现def wiggleMaxLength(nums): if not nums: return 0 n len(nums) if n 1: return 1 prev_diff nums[1] - nums[0] count 2 if prev_diff ! 0 else 1 for i in range(2, n): curr_diff nums[i] - nums[i-1] if (curr_diff 0 and prev_diff 0) or (curr_diff 0 and prev_diff 0): count 1 prev_diff curr_diff return count3.3 算法正确性证明贪心算法的正确性基于以下观察摆动序列的长度等于峰和谷的数量加1我们只需要在差值符号变化时增加计数跳过中间元素不会影响最终结果因为它们不会增加新的峰或谷这种方法确保了我们在O(n)时间内找到最优解因为每个元素最多被检查一次。4. 动态规划解法4.1 双状态DP思路虽然贪心算法更高效但动态规划解法也值得了解因为它展示了更通用的解题思路。我们可以维护两个数组up[i]表示到第i个元素为止最后是上升摆动的最长子序列长度down[i]表示到第i个元素为止最后是下降摆动的最长子序列长度状态转移方程为如果nums[i] nums[i-1]则up[i] down[i-1] 1down[i] down[i-1]如果nums[i] nums[i-1]则down[i] up[i-1] 1up[i] up[i-1]如果相等则两个状态都保持不变4.2 DP代码实现def wiggleMaxLength(nums): if not nums: return 0 n len(nums) up [1] * n down [1] * n for i in range(1, n): if nums[i] nums[i-1]: up[i] down[i-1] 1 down[i] down[i-1] elif nums[i] nums[i-1]: down[i] up[i-1] 1 up[i] up[i-1] else: up[i] up[i-1] down[i] down[i-1] return max(up[-1], down[-1])4.3 DP空间优化注意到每个状态只依赖于前一个状态可以进一步优化空间复杂度def wiggleMaxLength(nums): if not nums: return 0 n len(nums) up down 1 for i in range(1, n): if nums[i] nums[i-1]: up down 1 elif nums[i] nums[i-1]: down up 1 return max(up, down)5. 实际应用与变种问题5.1 股票买卖时机选择摆动序列的思想可以应用于股票买卖时机的选择。寻找股价序列中的峰和谷可以帮助确定最佳的买入和卖出点。这与摆动序列寻找交替极值的思路高度一致。5.2 信号处理中的极值检测在信号处理领域检测时间序列数据的极值点是一个常见任务。摆动序列算法可以用于识别信号中的关键转折点这在心电图分析、振动监测等场景中非常有用。5.3 变种问题非严格摆动序列如果题目放宽条件允许差值为0即相邻元素可以相等算法需要相应调整。此时贪心算法的条件判断需要修改为if (curr_diff 0 and prev_diff 0) or (curr_diff 0 and prev_diff 0):5.4 变种问题最长湍流子数组LeetCode第978题最长湍流子数组是摆动序列的一个变种要求找到最长的连续子数组作为湍流数组。解题思路类似但需要处理连续子数组的限制条件。6. 算法优化与调试技巧6.1 调试常见错误在实现摆动序列算法时容易犯以下错误忽略初始两个元素相等的情况错误处理数组长度为1或2的边界情况在贪心算法中过早更新prev_diff在动态规划中错误初始化dp数组6.2 测试用例设计全面的测试用例应该包括空数组单元素数组两元素数组相等和不等完全递增或递减的数组包含连续相等元素的数组标准的摆动序列长随机序列6.3 性能优化建议虽然贪心算法已经是O(n)时间复杂度但在实际实现中还可以提前终止遍历如果剩余元素不足以超过当前最大值可以提前结束使用指针代替数组索引访问减少边界检查对于非常大的数组可以考虑并行处理分段7. 不同语言实现对比7.1 Java实现public int wiggleMaxLength(int[] nums) { if (nums.length 2) return nums.length; int prevDiff nums[1] - nums[0]; int count prevDiff ! 0 ? 2 : 1; for (int i 2; i nums.length; i) { int diff nums[i] - nums[i-1]; if ((diff 0 prevDiff 0) || (diff 0 prevDiff 0)) { count; prevDiff diff; } } return count; }7.2 C实现int wiggleMaxLength(vectorint nums) { if (nums.size() 2) return nums.size(); int prev_diff nums[1] - nums[0]; int count prev_diff ! 0 ? 2 : 1; for (int i 2; i nums.size(); i) { int diff nums[i] - nums[i-1]; if ((diff 0 prev_diff 0) || (diff 0 prev_diff 0)) { count; prev_diff diff; } } return count; }7.3 JavaScript实现function wiggleMaxLength(nums) { if (nums.length 2) return nums.length; let prevDiff nums[1] - nums[0]; let count prevDiff ! 0 ? 2 : 1; for (let i 2; i nums.length; i) { const diff nums[i] - nums[i-1]; if ((diff 0 prevDiff 0) || (diff 0 prevDiff 0)) { count; prevDiff diff; } } return count; }8. 复杂度分析与算法选择8.1 时间复杂度对比贪心算法O(n)单次遍历数组动态规划O(n)但常数因子略高于贪心暴力法O(2^n)检查所有子序列实际不可行8.2 空间复杂度对比贪心算法O(1)只使用常数空间动态规划基础版O(n)需要两个长度为n的数组优化版O(1)类似贪心8.3 如何选择算法在实际应用中面试场景优先实现贪心算法可以讨论动态规划作为备选编程竞赛选择编码更简单的贪心算法教学场景可以两种都实现比较优缺点生产环境根据语言特性选择最简洁高效的实现9. 实际编码中的注意事项9.1 整数溢出问题当处理极大或极小的整数时差值计算可能导致溢出。例如prev_diff nums[1] - nums[0] # 如果nums[1]是INT_MINnums[0]是INT_MAX安全的做法是使用更大范围的整数类型或进行边界检查。9.2 浮点数比较如果数组包含浮点数直接比较差值可能不准确应该使用误差容忍度if abs(curr_diff) 1e-9 and ((curr_diff 1e-9 and prev_diff -1e-9) or ...):9.3 代码可读性优化可以通过定义枚举或常量来提高代码可读性UP, DOWN, EQUAL 1, -1, 0 def wiggleMaxLength(nums): if len(nums) 2: return len(nums) direction UP if nums[1] nums[0] else (DOWN if nums[1] nums[0] else EQUAL) count 2 if direction ! EQUAL else 1 for i in range(2, len(nums)): new_direction UP if nums[i] nums[i-1] else (DOWN if nums[i] nums[i-1] else EQUAL) if new_direction ! EQUAL and new_direction ! direction: count 1 direction new_direction return count10. 扩展思考与练习题10.1 相关LeetCode题目摆动序列 IILeetCode 324在O(n)时间和/或O(1)空间内摆动排序数组最长湍流子数组LeetCode 978连续子数组版本的摆动序列买卖股票的最佳时机系列多题类似极值检测思想10.2 理论延伸摆动序列问题可以关联到极值理论寻找序列中的局部最大值和最小值信号处理峰值检测和噪声过滤趋势分析识别时间序列数据中的转折点10.3 编程练习建议尝试实现所有讨论的变种和优化编写单元测试覆盖所有边界条件比较不同语言实现的性能差异尝试解决相关题目并分析它们的共性和差异在实际编程面试中理解摆动序列问题的各种解法和变种能够展示出对算法问题的深入理解和灵活应用能力。掌握这类问题的核心在于识别其贪心性质并能够正确处理各种边界条件。