1. 贪心算法实战三部曲从引爆气球到区间划分今天咱们来聊聊LeetCode上三个经典的贪心算法问题——用最少数量的箭引爆气球、无重叠区间和划分字母区间。这三个问题看似不同实则都体现了贪心算法的核心思想通过局部最优选择达到全局最优解。作为刷过300LeetCode题的老手我发现很多初学者在这类问题上容易陷入暴力求解的误区而贪心算法往往能提供更优雅的解决方案。2. 452. 用最少数量的箭引爆气球2.1 问题重述与直观理解给定在水平方向上排列的气球每个气球用区间[xstart, xend]表示其水平直径范围。如果一支箭沿垂直方向射出只要满足xstart ≤ arrow ≤ xend气球就会被引爆。我们的目标是找到射出箭的最小数量使所有气球都被引爆。想象你在游乐场玩射气球游戏一排气球飘在空中你希望用最少的箭把它们全部射爆。这就是问题的现实场景。2.2 贪心策略的思考过程最直观的解法可能是每次找到一个能射爆最多气球的箭的位置。但如何高效实现这个思路排序是关键首先按气球的结束坐标升序排序。这样我们可以确保每次射箭的位置尽可能靠右从而覆盖更多后续气球。射箭位置选择初始化第一支箭在第一个气球的结束位置。然后遍历后续气球如果当前气球的开始位置 当前箭的位置说明这支箭可以射爆它否则需要新增一支箭位置设为此气球的结束位置2.3 代码实现与复杂度分析def findMinArrowShots(points): if not points: return 0 # 按结束坐标升序排序 points.sort(keylambda x: x[1]) arrows 1 first_end points[0][1] for start, end in points: # 如果当前气球开始于上一支箭的射程之外 if start first_end: arrows 1 first_end end return arrows时间复杂度O(nlogn)排序占主导 空间复杂度O(1)原地排序时为O(1)否则为O(n)关键提示排序时一定要按结束坐标排序而不是开始坐标。这是贪心选择的核心所在。2.4 常见错误与边界情况空输入处理题目没说points不为空需要单独处理整数溢出虽然Python不用担心但其他语言要注意xstart和xend可能很大单气球情况显然只需要一支箭完全重叠气球所有气球区间相同只需一支箭3. 435. 无重叠区间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 interval in intervals[1:]: if interval[0] end: count 1 end interval[1] return len(intervals) - count3.3 为什么这种贪心选择有效关键在于每次选择结束最早的区间为后续选择留出最大空间。这保证了局部最优能导向全局最优。可以数学归纳法证明其正确性。3.4 实际应用场景课程安排在有限时间内安排最多课程任务调度在单核CPU上安排最多不冲突任务资源分配最大化利用共享资源4. 763. 划分字母区间4.1 问题特点分析给定字符串S将其划分为尽可能多的片段使得每个字母最多出现在一个片段中。要求返回这些片段的长度列表。这实际上是要找到字符串中每个字母的最后出现位置然后根据这些信息进行划分。4.2 贪心算法的两步走策略记录最后位置首先遍历字符串记录每个字符最后出现的位置动态扩展区间初始化当前区间的start和end遍历字符串不断扩展end为当前字符的最后位置当i end时说明找到一个完整区间def partitionLabels(S): last {c: i for i, c in enumerate(S)} start end 0 result [] for i, c in enumerate(S): end max(end, last[c]) if i end: result.append(end - start 1) start i 1 return result4.3 复杂度与优化时间复杂度O(n)两次线性遍历 空间复杂度O(1)因为字母数量固定最多26个4.4 实际应用价值分布式计算中的数据分区内存管理中的对象分配文本处理中的段落划分5. 贪心算法解题的通用模式通过这三个问题我们可以总结出贪心算法解决区间问题的通用模式排序预处理通常需要按开始或结束位置排序贪心选择标准选择结束最早或开始最晚的区间迭代处理维护当前关键位置遍历并做选择结果收集在适当时候记录结果贪心算法不是万能的它适用于具有贪心选择性质的问题。在面试中当遇到最少、最多、最优等关键词时可以考虑贪心算法是否适用。我在实际刷题中发现贪心算法的问题往往代码简洁但思路巧妙。建议初学者多练习这类问题培养对贪心选择性质的敏感度。对于这三个问题可以尝试先自己思考解法再对比最优解体会贪心选择的精妙之处。