1. 贪心算法核心思想回顾在进入具体问题之前我们先明确贪心算法的基本特征。这种算法在每一步选择中都采取当前状态下最优的决策希望通过局部最优解的累积达到全局最优。与动态规划不同贪心算法不会回退这也决定了它并非适用于所有问题场景。贪心算法有效的三个关键前提条件贪心选择性质局部最优解能导致全局最优解最优子结构问题的最优解包含子问题的最优解无后效性某个状态以前的过程不会影响后续决策注意实际应用中需要严格证明问题满足这些条件否则可能得到错误结果。很多初学者容易忽略这一点。2. 分发糖果问题解析2.1 问题描述与建模假设有N个孩子排成一列每个孩子有一个评分值。要求每个孩子至少分到1颗糖评分更高的孩子必须比相邻孩子获得更多糖果求最少需要准备的糖果总数这个问题可以抽象为在满足相邻约束条件下寻找一个非负整数序列的最小和。关键在于如何处理相邻比较产生的矛盾约束。2.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] * n for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: right[i] right[i1] 1 return sum(max(left[i], right[i]) for i in range(n))时间复杂度O(n)空间复杂度O(n)。这种双向处理巧妙地解决了单向遍历无法兼顾两边约束的问题。2.3 常数空间优化实际上可以优化到O(1)空间def candy(ratings): n len(ratings) res 1 inc, dec, pre 1, 0, 1 for i in range(1, n): if ratings[i] ratings[i-1]: dec 0 pre (1 if ratings[i] ratings[i-1] else pre 1) res pre inc pre else: dec 1 if dec inc: dec 1 res dec pre 1 return res这个优化版本通过记录当前递增/递减序列长度来动态计算糖果数适合处理大规模数据。3. 无重叠区间问题3.1 问题转化思路给定一组区间要求移除最少数量的区间使剩余区间互不重叠。这可以转化为选择最多不重叠区间的问题是典型的区间调度问题。关键思路按照结束时间排序优先选择结束早的区间为后续选择留出更多空间。3.2 贪心策略实现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)。这种策略的正确性基于选择结束最早的区间可以为后续留下最大的选择空间。3.3 不同排序方式的对比实践中也可以尝试按开始时间排序intervals.sort(keylambda x: x[0]) end intervals[0][1] count 1 for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] else: end min(end, intervals[i][1])这种实现需要更复杂的end值维护但同样有效。两种方法在不同场景下各有优势。4. 合并区间问题4.1 问题特征分析给定一组可能重叠的区间合并所有重叠的区间。这与前一个问题形成对比需要处理的是重叠而非分离。关键观察排序后可以线性时间完成合并因为重叠区间必然连续。4.2 标准解法实现def merge(intervals): intervals.sort(keylambda x: x[0]) merged [] for interval in intervals: if not merged or merged[-1][1] interval[0]: merged.append(interval) else: merged[-1][1] max(merged[-1][1], interval[1]) return merged时间复杂度O(nlogn)主要来自排序步骤。空间复杂度O(n)用于存储结果。4.3 边界情况处理需要特别注意的边界情况空输入列表单元素区间完全包含的区间如[1,4]和[2,3]刚好相接但不重叠的区间如[1,2]和[2,3]代码中的max操作确保了完全包含情况的正确处理。5. 贪心算法应用心得在实际工程中应用贪心算法时有几个关键经验证明优先一定要先确认问题满足贪心选择性质不能凭直觉假设排序是常见预处理许多贪心问题都需要先对数据进行某种排序画图辅助对于区间类问题绘制时间线图能帮助理解最优策略测试极端情况空输入、全等元素、完全包含等情况最容易出问题空间优化可能很多问题都有从O(n)到O(1)的空间优化空间对于区间问题的通用处理模式确定排序依据开始时间或结束时间设计选择策略取最早结束或最晚开始处理重叠/非重叠条件考虑是否需要双向处理贪心算法虽然思想简单但要写出高效正确的实现需要对这些模式有深刻理解和大量练习。建议从LeetCode的贪心算法专题入手系统性地刷题培养直觉。