1. 贪心算法专题训练概述作为算法训练营第31天的内容这个专题聚焦贪心算法(Greedy Algorithm)的核心应用场景与解题技巧。贪心算法在解决最优化问题时表现出独特的优势——它通过每一步的局部最优选择希望达到全局最优解。这种短视的策略虽然不保证所有情况下都能得到最优解但在许多实际问题中却能以极高的效率给出令人满意的答案。我在实际刷题和算法教学中发现贪心算法最容易让初学者产生两种误解要么过度依赖直觉导致解题错误要么因为无法证明正确性而不敢使用。这个专题正是要帮助大家建立对贪心算法的系统性认知掌握其适用场景和实现要点。2. 贪心算法的核心特征与应用场景2.1 贪心算法的三大特征贪心算法区别于其他算法的核心特征在于局部最优选择每个步骤都做出当前看来最佳的选择无后效性当前选择不会影响后续子问题的结构不可回退一旦做出选择就不能改变典型的适用场景包括区间调度问题如会议室安排霍夫曼编码最小生成树Prim和Kruskal算法最短路径Dijkstra算法2.2 贪心算法的正确性证明很多同学在使用贪心算法时最大的困惑就是如何证明其正确性。常见证明方法包括数学归纳法证明贪心选择在每一步都保持最优子结构交换论证证明任何非贪心选择都可以被贪心选择替代而不劣化结果反证法假设存在更优解推导出矛盾提示在实际刷题中如果无法严格证明可以通过举反例的方式验证贪心策略的正确性。这是面试中常用的快速验证方法。3. 贪心专题5的典型题目解析3.1 区间问题系列区间问题是贪心算法的经典应用场景。以无重叠区间为例问题描述 给定一个区间集合找到需要移除区间的最小数量使剩余区间互不重叠。贪心策略按区间右端点排序每次选择右端点最小且不与前一个选中区间重叠的区间def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) count 1 end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] return len(intervals) - count复杂度分析时间复杂度O(nlogn)主要来自排序空间复杂度O(1)3.2 分发糖果问题这个问题展示了贪心算法需要双向处理的特殊情况问题描述 老师要给孩子们分发糖果每个孩子至少一个糖果。相邻孩子中评分高的必须获得更多糖果。解题思路从左到右遍历确保右边高分孩子比左边多从右到左遍历确保左边高分孩子比右边多取两次遍历结果的较大值def candy(ratings): n len(ratings) left [1] * n for i in range(1, n): if ratings[i] ratings[i-1]: left[i] left[i-1] 1 right 1 res max(left[-1], right) for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: right 1 else: right 1 res max(left[i], right) return res4. 贪心算法的常见陷阱与优化技巧4.1 贪心选择性的误判最常见的错误是错误判断问题是否具有贪心选择性。例如在硬币找零问题中对于常规硬币面额如1,5,10,25贪心算法有效对于特殊面额如1,3,4贪心算法可能失效反例 找零6元贪心选择411共3枚实际最优解是33共2枚4.2 处理特殊边界条件贪心算法对边界条件特别敏感。以跳跃游戏为例def canJump(nums): max_reach 0 for i in range(len(nums)): if i max_reach: return False max_reach max(max_reach, i nums[i]) return True易错点初始位置是否为0的判断数组长度为1时的特殊情况最大可达距离等于当前位置时的处理4.3 贪心与其他算法的结合有时贪心需要与其他算法结合使用。例如在任务调度器问题中统计每种任务的数量优先安排数量最多的任务使用数学公式计算最短时间def leastInterval(tasks, n): freq [0] * 26 for t in tasks: freq[ord(t) - ord(A)] 1 freq.sort() max_freq freq[-1] idle_slots (max_freq - 1) * n for i in range(24, -1, -1): if freq[i] 0: continue idle_slots - min(max_freq - 1, freq[i]) if idle_slots 0: break return len(tasks) max(0, idle_slots)5. 贪心算法的进阶应用5.1 带权区间调度在基础区间问题上的扩展每个区间有权重目标是选择不重叠区间使总权重最大。这类问题通常需要动态规划与贪心思想结合按结束时间排序使用二分查找找到与当前区间兼容的前一个区间比较包含当前区间和不包含当前区间两种情况5.2 多机调度问题将n个作业分配到m台机器上使完成所有作业的时间最短。这是一个NP难问题但贪心算法可以提供近似解将作业按处理时间降序排列每次将当前作业分配给最早空闲的机器def findMinimumTime(tasks, m): heap [0] * m heapq.heapify(heap) tasks.sort(reverseTrue) for task in tasks: earliest heapq.heappop(heap) heapq.heappush(heap, earliest task) return max(heap)6. 贪心算法的面试准备建议6.1 高频贪心问题分类根据我的面试经验贪心算法问题大致可分为以下几类分配问题如分糖果、分饼干区间问题会议室安排、无重叠区间跳跃游戏系列买卖股票系列字符串重组问题6.2 解题思路模板面对新的贪心问题时可以按照以下步骤思考分析问题是否具有最优子结构尝试提出贪心选择策略举例子验证策略的正确性考虑边界条件和特殊情况编写代码实现6.3 复杂度优化技巧贪心算法本身通常已经很高效但仍有优化空间优先考虑排序的替代方案如计数排序使用堆来维护当前最优选择双指针技巧减少不必要的遍历预处理数据以加速后续操作我在算法教学中发现很多同学在实现贪心算法时容易陷入过度设计的误区。实际上贪心算法的优势就在于它的简洁性。与其追求复杂的优化不如先把基础的贪心策略想清楚这往往能带来更好的效果。