1. 摆动序列问题解析最近在刷算法题时遇到了一个有趣的问题——摆动序列。这个问题看似简单但想要高效解决却需要深入理解贪心算法的思想。摆动序列的定义是如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。举个例子序列[1,7,4,9,2,5]就是一个摆动序列因为差值(6,-3,5,-7,3)交替变化。而[1,4,7,2,5]不是摆动序列因为前两个差值都是正数(3,3,-5,3)。2. 贪心算法思路拆解2.1 贪心算法的基本思想贪心算法是一种在每一步选择中都采取当前状态下最优的选择从而希望导致结果是全局最优的算法。它不像动态规划那样考虑所有可能的子问题而是做出局部最优选择期望这些选择能导致全局最优解。对于摆动序列问题贪心算法的适用性在于我们只需要关注序列中峰和谷的位置而不需要考虑中间过渡的数字。这种局部最优选择最终会导致全局最优解。2.2 摆动序列的贪心解法具体到摆动序列问题我们可以这样思考我们需要统计序列中峰和谷的数量一个峰是指当前数字比前后数字都大一个谷是指当前数字比前后数字都小序列两端的数字可以视为特殊的峰或谷通过这种思路我们只需要遍历一次序列记录下这些转折点即可得到最长摆动子序列的长度。3. 算法实现与优化3.1 基础实现方法最直观的实现方式是使用两个变量分别记录前一个差值和当前差值def wiggleMaxLength(nums): if len(nums) 2: return len(nums) prev_diff nums[1] - nums[0] count 2 if prev_diff ! 0 else 1 for i in range(2, len(nums)): 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 count这个实现的时间复杂度是O(n)空间复杂度是O(1)已经相当高效。3.2 优化思路我们可以进一步优化代码使其更加简洁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)这个优化版本使用两个变量up和down来分别记录以当前元素为上升结尾和下降结尾的最长子序列长度。4. 实际应用与边界情况4.1 实际应用场景摆动序列问题在实际中有很多应用场景股票价格分析寻找价格波动较大的时期信号处理检测信号中的转折点路径规划寻找路径中的关键转折点4.2 边界情况处理在实现算法时需要特别注意以下边界情况空序列或单元素序列直接返回0或1所有元素相同返回1序列开头有多个相同元素需要正确处理初始状态序列中间有连续相同元素需要跳过不影响摆动计数5. 算法复杂度分析5.1 时间复杂度两种实现方式都是线性扫描整个数组一次因此时间复杂度都是O(n)其中n是数组的长度。5.2 空间复杂度两种实现都只使用了常数个额外变量因此空间复杂度都是O(1)。6. 常见错误与调试技巧6.1 常见错误忽略初始条件忘记处理数组长度小于2的情况错误处理相等情况当连续数字相等时处理不当更新条件错误在错误的时间更新prev_diff变量6.2 调试技巧打印中间变量在循环中打印prev_diff和curr_diff的值使用小测试用例先用简单的例子验证算法正确性边界测试专门测试空数组、单元素数组等边界情况7. 算法扩展与变种7.1 最长摆动子序列这个问题的一个变种是寻找最长摆动子序列而不仅仅是计算长度。这需要稍微修改算法记录下实际的序列元素。7.2 其他变种允许摆动幅度在一定范围内考虑摆动频率限制多维摆动序列问题8. 个人实现心得在实际编码实现这个算法时我发现以下几点特别重要初始条件的处理要小心特别是数组长度小于2的情况相等的相邻元素应该被跳过不影响摆动计数更新prev_diff的时机很关键只有在发现摆动时才需要更新第二种优化方法虽然简洁但理解起来需要更多思考通过这个问题的练习我对贪心算法的理解更加深入了。贪心算法不是万能的但在适合的问题上它能提供非常高效的解决方案。关键在于识别问题是否具有贪心选择性质即局部最优解能否导致全局最优解。