贪心算法实战：分发饼干、摆动序列与最大子序和解析

1. 算法训练营Day25贪心算法实战精解今天要啃下三道经典的贪心算法题目分发饼干、摆动序列和最大子序和。作为代码随想录训练营的第25天内容这三个题目完美展现了贪心算法局部最优推导全局最优的核心思想。我在刷题过程中发现很多同学卡在贪心策略的证明环节其实只要掌握好问题拆解的技巧这类题目都有清晰的解题路径。2. 分发饼干问题解析2.1 问题本质与贪心策略题目描述有一群孩子和一堆饼干每个孩子有满足度g_i每块饼干有大小s_j。只有当s_j g_i时才能分配求最多能满足多少孩子。贪心策略的核心在于排序将孩子和饼干分别按满足度、尺寸升序排序用最小的饼干优先满足最容易满足的孩子def findContentChildren(g, s): g.sort() s.sort() child cookie 0 while child len(g) and cookie len(s): if s[cookie] g[child]: child 1 cookie 1 return child2.2 关键证明与复杂度分析为什么这个策略最优假设存在更优解那么至少有一个孩子被更大的饼干满足但这样会浪费大饼干的满足能力。时间复杂度O(nlogn)来自排序空间O(1)。实战注意Python的sort()是Timsort算法最坏情况也是O(nlogn)3. 摆动序列问题精讲3.1 问题转化与状态机思想求最长摆动子序列长度即相邻数字差正负交替。例如[1,7,4,9,2,5]的摆动序列长度为6。贪心解法不需要删除元素只需统计极值点维护当前差值趋势上升/下降当趋势发生合法变化时计数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)): diff nums[i] - nums[i-1] if (diff 0 and prev_diff 0) or (diff 0 and prev_diff 0): count 1 prev_diff diff return count3.2 边界情况处理平坡情况[3,3,3,2,5] 应该返回3两元素相同返回1空数组返回04. 最大子序和问题突破4.1 贪心与动态规划的抉择求连续子数组的最大和。贪心解法维护当前累加和当累加和为负时立即重置因为负数会拖累后续和始终记录最大值def maxSubArray(nums): max_sum current_sum nums[0] for num in nums[1:]: current_sum max(num, current_sum num) max_sum max(max_sum, current_sum) return max_sum4.2 算法正确性证明假设最优解某前缀和为负那么去掉该前缀能得到更大和与最优解矛盾。因此当当前和变负时必须重置。复杂度O(n)优于分治法的O(nlogn)空间O(1)。5. 贪心算法通用解题框架通过这三题可以总结贪心算法的解题模式问题分解将大问题拆解为多个局部阶段贪心选择确定每个阶段的局部最优策略正确性证明通常用反证法证明局部最优能导致全局最优避坑指南贪心算法不是万能的必须满足贪心选择性质局部最优能导致全局最优。当不确定时可以先尝试举反例。6. 代码随想录训练建议根据我的刷题经验建议这样使用代码随想录先独立思考15分钟写出初始解法对比讲解检查思路盲点手写代码并测试边界条件记录同类题目如今天的题目都可以用贪心思想例如相关扩展题跳跃游戏LeetCode 55加油站LeetCode 134根据身高重建队列LeetCode 406最后分享一个调试技巧对于贪心算法可以在决策点打印关键变量比如在最大子序和问题中打印current_sum和max_sum的变化过程这样能直观看到贪心策略的执行逻辑。