1. 贪心算法核心思想解析贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优决策的算法策略。它不像动态规划那样考虑全局最优解而是通过局部最优选择的累积来逼近全局最优。这种短视的特性使得贪心算法在解决特定类型问题时异常高效。我在刷LeetCode Hot 100题目时发现大约有15%的题目可以通过贪心策略高效解决。典型的贪心问题往往具有最优子结构特性——即一个问题的最优解包含其子问题的最优解。例如在找零钱问题中如果我们有足够多的25美分硬币那么先用大面额硬币支付就是典型的贪心选择。关键识别特征当问题可以通过一系列局部最优选择达到全局最优且不需要回溯时就适合用贪心算法。2. LeetCode Hot 100中的经典贪心题型2.1 区间调度类问题这类问题通常需要在一组区间中选择最大数量的互不重叠区间。LeetCode第435题无重叠区间就是典型代表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为什么按结束时间排序因为这样能保证每次选择结束后最早释放资源的区间为后续选择留下最大空间。这是典型的贪心选择性质。2.2 分配类问题LeetCode第455题分发饼干展示了如何用贪心思想解决分配问题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 child双指针技巧将孩子和饼干都按大小排序后用双指针遍历确保每个孩子得到能满足其需求的最小饼干。这种刚好满足的策略避免了资源浪费。2.3 跳跃游戏类问题LeetCode第55题跳跃游戏和第45题跳跃游戏II是考察贪心算法的经典题目# 跳跃游戏I - 判断能否到达终点 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 # 跳跃游戏II - 最少步数到达终点 def jump(nums): jumps 0 current_end 0 farthest 0 for i in range(len(nums)-1): farthest max(farthest, i nums[i]) if i current_end: jumps 1 current_end farthest return jumps贪心选择原理在每一步都选择能跳得最远的位置这样能保证整体跳跃次数最少。这种最远可达的思想是贪心算法的精髓。3. 贪心算法的解题框架与技巧3.1 四步解题法问题分解将问题分解为一系列子问题贪心选择确定每个子问题的最优选择标准可行性验证证明局部最优能导致全局最优算法实现用代码实现贪心策略3.2 常见贪心策略排序预处理大多数贪心问题都需要先对数据进行排序如按结束时间、起始位置、数值大小等双指针技巧常用于处理有序数组的贪心问题区间合并处理区间问题时常用合并重叠区间的方法优先队列当需要动态获取当前最优选择时使用3.3 贪心算法的局限性贪心算法不能解决所有问题它适用于具有贪心选择性质和最优子结构的问题。例如经典的0-1背包问题就不能用贪心算法解决因为局部最优价值密度最高不一定导致全局最优。4. LeetCode Hot 100贪心题目精讲4.1 买卖股票的最佳时机II第122题def maxProfit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i-1]: profit prices[i] - prices[i-1] return profit贪心思想只要今天的价格比昨天高就进行交易。虽然现实中不可能预知未来价格但在题目设定下这种策略能获得最大利润。4.2 加油站问题第134题def canCompleteCircuit(gas, cost): total_tank curr_tank 0 start 0 for i in range(len(gas)): total_tank gas[i] - cost[i] curr_tank gas[i] - cost[i] if curr_tank 0: start i 1 curr_tank 0 return start if total_tank 0 else -1关键观察如果从加油站A出发无法到达加油站B那么A和B之间的任何站点都不能作为起点。这个性质使得我们可以用贪心策略选择起点。4.3 划分字母区间第763题def partitionLabels(S): last {c: i for i, c in enumerate(S)} start end 0 res [] for i, c in enumerate(S): end max(end, last[c]) if i end: res.append(end - start 1) start i 1 return res贪心策略记录每个字母最后出现的位置在遍历时维护当前片段的结束边界。当遍历到边界时说明找到了一个符合要求的片段。5. 贪心算法常见错误与调试技巧5.1 典型错误类型错误识别问题性质将不适合贪心的问题强行用贪心解决贪心策略设计错误选择的局部最优标准不能导致全局最优边界条件处理不当特别是处理空输入或极端情况时出错5.2 调试方法小规模测试用简单的测试用例手动验证算法步骤打印中间结果在关键决策点打印变量值对比法将贪心结果与暴力解法结果对比适用于小规模问题5.3 贪心算法的证明技巧交换论证法证明任何非贪心的选择都可以通过交换调整为贪心选择而不降低解的质量数学归纳法证明贪心选择在每一步都保持最优性决策树分析展示所有可能的决策路径中贪心路径最优6. 贪心算法与其他算法的比较6.1 贪心 vs 动态规划贪心算法与动态规划都用于优化问题但贪心不回溯动态规划则通过保存子问题解来避免重复计算。例如分数背包问题可以用贪心而0-1背包必须用动态规划。6.2 贪心 vs 回溯回溯法会尝试所有可能的解而贪心算法一旦做出选择就不改变。回溯法能解决更广泛的问题但时间复杂度通常更高。6.3 贪心 vs 分治分治算法将问题分解为独立的子问题而贪心算法的子问题通常是相互关联的。分治法的经典例子是归并排序而贪心法的例子是霍夫曼编码。7. 进阶贪心问题解析7.1 任务调度器第621题def leastInterval(tasks, n): freq [0] * 26 for t in tasks: freq[ord(t) - ord(A)] 1 freq.sort() max_freq freq[25] - 1 idle_slots max_freq * n for i in range(24, -1, -1): if freq[i] 0: idle_slots - min(freq[i], max_freq) return len(tasks) idle_slots if idle_slots 0 else len(tasks)贪心策略优先安排出现次数最多的任务然后利用其他任务填充冷却时间。这种策略能最小化总体等待时间。7.2 去除K位数字第402题def removeKdigits(num, k): stack [] for digit in num: while k 0 and stack and stack[-1] digit: stack.pop() k - 1 stack.append(digit) final_stack stack[:-k] if k 0 else stack return .join(final_stack).lstrip(0) or 0单调栈技巧维护一个单调递增的栈当遇到比栈顶小的数字时弹出栈顶贪心地移除更大的数字。这种策略能保证剩下的数字最小。7.3 重构字符串第767题def reorganizeString(S): freq sorted([(S.count(c), c) for c in set(S)], reverseTrue) if freq[0][0] (len(S) 1) // 2: return res [None] * len(S) i 0 for count, c in freq: for _ in range(count): if i len(S): i 1 res[i] c i 2 return .join(res)间隔放置策略先统计字符频率然后按频率从高到低将字符间隔放置到结果数组中。这种贪心策略能有效避免相同字符相邻。