贪心算法实战指南：从局部最优到全局最优的经典例题

今天是我"更弱智的算法学习"系列的第23天。这个名字不是自暴自弃，而是我自己总结出来的一套学习策略：把自己当成一个什么都不懂、只会用最笨办法的人，先把一个算法用最朴素的方式跑通，再去理解它背后的道理。今天这个位置，刚好轮到算法学习路上绕不开的"贪心算法"。如果你在网上搜算法相关内容，大概率会看到"贪心算法"这个关键词和"动态规划""剪枝算法""KMP"一起出现在推荐列表里。这篇博文就记录我第23天的完整学习过程，从翻车到理解，顺便帮同样被贪心搞晕的人少走几条弯路。

1. Day 23 的开场白：为什么我管贪心叫"弱智"算法

1.1 一道硬币找零题让我当场翻车

我一开始以为贪心就是"每一步选最好"。于是打开一道硬币找零题。假设硬币面值只有1、3、4，要凑出6。我的第一反应是：先选4，还差2；再选1，还差1；再选1。结果用了3枚硬币。但人肉看一眼就知道，正确答案是3+3，只要2枚。当场翻车。这说明"每一步选最好"在有些情况下根本不成立，问题出在"这一步选得最好，后面就没得选"。

这个例子我后来一直记着，它帮我区分了"贪心"和"感觉"的区别。如果你觉得自己已经理解贪心算法，不妨先拿这个例子考一下自己。它虽然简单，却浓缩了贪心最容易犯错的地方：局部最优并不自动等于全局最优。

1.2 贪心到底是什么：不是"闭眼乱选"

贪心的正规说法是：在每一步决策时，只考虑当前状态下的局部最优选择，并期望这些局部最优能叠加成全局最优。"期望"两个字是重点。很多初学者把贪心理解为"闭眼乱选"，其实贪心是对"选择规则"有严格要求的算法，只是它不做回溯，不重新考虑之前的决定。

用生活例子类比：找工作。手头有一批Offer，贪心策略就是选当下薪水最高的，签完不回头。这个策略在某些市场里是合理的，但如果后续出现一个"成长性更好"或"期权价值更高"的公司，贪心就会错过。算法题里的道理一模一样，你以为你选的是全局最优，其实只看到了当前这一步。

1.3 今天这篇适合谁读

如果你刚开始学算法，被"贪心算法""动态规划""回溯"这些术语吓到，这篇适合你。如果你已经刷了一段时间题，但拿到一个陌生题目还是不知道"该不该贪心"，这篇也适合。我假设你已经会写基本的循环和数组，但完全没接触过贪心也没关系，跟着例子走就能理解。我还会尽量少用复杂的数学证明，多讲直觉、反例、代码，把贪心从"玄学"变成可以按步骤执行的判断方法。当然，如果你已经能熟练证明贪心正确性，可以直接跳到第4章看总结。

2. 贪心成立的底层逻辑：局部最优怎么变成全局最优

2.1 找零钱为什么是反面教材

还是回到硬币面值[1,3,4]、目标金额6的例子。贪心选择过程是：第一次选最大的4，剩余2；第二次只能选1，剩余1；第三次再选1，结束。硬币数=3。最优方案是：选3，剩余3；再选3，结束。硬币数=2。为什么贪心失败？因为在面值1、3、4之间，不存在一种"谁大谁就绝对划算"的结构。4虽然单个面值大，但它和3的组合相比，占用了太多"凑数空间"。换句话说，局部最优（选最大面值）没有保持剩余子问题的最优性。

一个面值体系如果可以贪心，通常要求满足某种倍数关系，比如1、5、10、25，每个大面值都能被小面值凑出来，这样大面值不会"浪费"组合可能。所以学贪心，第一步不是背模板，而是理解"为什么有些选择看起来贪心实际坑"。

2.2 活动选择问题：贪心正确性的完整证明

活动选择问题是贪心最经典的正面教材。设有一组活动，每个有开始时间s[i]和结束时间f[i]，选择最多数量的互不重叠活动。贪心规则：按结束时间从小到大排序，然后依次选择第一个与已选活动兼容的活动。

我来说服自己为什么这一定最优：

1. 设最优解中第一个被选的活动是k，而贪心选择的是m。因为m在排序后出现最早，所以m的结束时间不大于k的结束时间。
2. 把最优解里的k换成m。由于m结束得不比k晚，所以原本排在k后面的所有活动，和m依然是兼容的。换完之后的活动集合数量和原来一样多。
3. 重复这个"替换"过程，最后得到的最优解就是从贪心第一步开始的最优解。因此贪心策略不会让结果变差。

这就是"交换论证"的思想。用生活类比：你在大厅排队参加各种短会议，碰到的第一个结束的会议一定可以安全接上其它任意会议，所以先选它不亏。

2.3 区间问题里的贪心套路

学会活动选择之后，很多区间题都从这个模型变形而来。常见的包括：

• 无重叠区间：按结束时间排序，能选就选，最后用总数减能选数量。
• 用最少数量的箭引爆气球：把气球看作区间，排序后尽可能用同一点覆盖更多区间。
• 合并区间：这个通常按开始时间排序，然后扫描合并。

注意一个关键区别：活动选择和无重叠区间这类"求最大不重叠数量"的问题，按结束时间排序；合并区间这类"求并集"问题，按开始时间排序。原因在于你想优化的是"数量还是连续性"：前者希望每个选择留出最多剩余空间，后者希望抓住所有可能重叠范围的起点。

3. 实战三道题，把贪心从"感觉"变"直觉"

3.1 分发饼干：排序后双指针的教科书操作

题目：每个孩子有一个胃口值g[i]，每个饼干有一个尺寸s[j]。每个孩子最多给一块饼干，且饼干尺寸大于等于胃口才能满足。求最多能满足几个孩子。

直觉：小饼干给小胃口，大饼干留着给大胃口，因为大饼干能覆盖的需求范围更大。做法：两个数组都排序，用两个指针，从最小的胃口和最小的饼干开始匹配。如果当前饼干能满足当前孩子，指针都前进，答案加一；如果不能，说明这块饼干太小，饼干指针前进换一块更大的。

def findContentChildren(g, s): g.sort() s.sort() i = j = 0 while i < len(g) and j < len(s): if s[j] >= g[i]: i += 1 j += 1 return i

这道题骗过很多人的地方在于：你可能会贪心地用最小饼干去满足最大胃口，结果发现小胃口没被利用，答案反而变小。排序之后按"最小满足当前最小"是对的，因为饼干分配顺序不影响可行性，但影响匹配数量。时间复杂度是排序主导的O(nlogn)，空间复杂度O(1)。

3.2 加油站：净消耗与总油量的关系

题目变成环形路线：每个加油站的油量gas[i]，从加油站i开到i+1需要消耗cost[i]。问从哪个站出发能绕一圈回来，如果不存在就返回-1。第一次看到这题，我想的是模拟每个起点，复杂度O(n^2)。后来发现一个漂亮的贪心思路。

先算每个站的净收益diff[i] = gas[i] - cost[i]。如果总收益total小于0，说明整个环的油不够，无论如何都走不完，直接返回-1。如果总收益大于等于0，那么一定存在一个可行起点。怎么找？从左到右遍历，用cur记录从当前起点出发跑到现在的剩余油量。一旦cur小于0，说明从当前起点到当前位置这一段没跑通。关键结论：这一段中的任何位置都不能作为全局起点。于是把起点暂定为i+1，cur清零，继续往后试。遍历完的start就是答案。

为什么中间任何位置都不能当起点？因为你的cur是"从start开始一路累加"的结果，如果cur在i处变成负数，说明从start出发到i的每段净收益，叠加在start点上是无法支撑到i的。如果从start和i之间的某个k点出发，相当于把前面这段的负收益丢掉了，但你丢失了从start到k可能积累的正收益，所以在i点依然会失败。这个"前缀亏空"是累积的，不能靠换起点躲过。

def canCompleteCircuit(gas, cost): total = 0 cur = 0 start = 0 for i in range(len(gas)): diff = gas[i] - cost[i] total += diff cur += diff if cur < 0: start = i + 1 cur = 0 return start if total >= 0 else -1

注意：不能在循环中间因为cur小于0直接返回-1，因为后面的总油量还没累计完，total可能被后面补回来。

3.3 跳跃游戏：从右往左的"最远距离"

跳跃游戏的描述：数组nums，每个元素代表你在该位置最多能跳多远，初始在下标0，问能否到达最后一个下标。这个题和动态规划、回溯都有关，但一个简单贪心就能解决：维护一个变量max_reach表示当前能到达的最远位置。遍历每个位置i：

• 如果i已经大于max_reach，说明这个位置根本不可达，直接返回False。
• 否则更新max_reach = max(max_reach, i + nums[i])。
• 一旦max_reach大于等于n-1，可以提前返回True。

为什么一次遍历就能判断？因为max_reach记录的是所有已访问位置中能延伸的最大右边界。在这个边界内，每个位置都是可达的；边界外的位置如果想可达，必须依赖某次跳跃把它覆盖进边界里。如果遍历到某个i时i > max_reach，说明没有任何已访问位置能跳到i，更不可能跳到后面。

def canJump(nums): n = len(nums) max_reach = 0 for i in range(n): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) if max_reach >= n - 1: return True return False

这是一个"正着贪"的题，和前面的活动选择一样，贪心的核心在于"维护一个单调扩大的可达范围"。它能成立是因为"跳跃能力"具有传递性：如果a能跳到b，b能跳到c，则a一定能通过b跳到c。这种传递性保证了局部选择不会污染全局状态。

4. 判断贪心可用性的四步法：我的排雷清单

4.1 子问题独立吗？

贪心最怕的情况是"这一步的选择会改变后面所有选择的条件"。如果选择完当前项后，解决剩余问题的场景和原问题结构完全一样，只是规模缩小，贪心才有戏。

活动选择是典型的独立子问题：选完最早结束的活动后，剩下的问题就是在更晚的时间窗口里继续选活动。而硬币找零的反例里，选4后剩余问题变成了"用1来填补2"，这个子问题和你有没有选3密切相关，两个子问题不是独立的。看到一个新题，先问自己：我做出第一步选择后，剩下的还是一个同构问题吗？

4.2 局部最优能传导到下一步吗？

更直白地问：这一步选了最优，下一步的最优还能利用这个选择吗？如果不能，那这一步的最优就是"假最优"。

拿爬山来类比：只看眼前最陡的坡往上爬，可能爬到一个小山包，四周都是悬崖，想再往上就得先下山。算法里的"下山重来"意味着要推翻之前的决策，贪心不允许这么干。所以只有"每一步都不会把路堵死"的选择才能贪心。比如分发饼干里，用最小饼干满足最小胃口，这一步不会堵死大饼干的去路，反而把大饼干释放给了大胃口。

4.3 能不能构造一个反例？

这是我在刷题时最常用的排雷手段。正式写代码前，先拿一个很小的测试用例手算一遍贪心，再努力构造一个让它失败的用例。如果能构造出来，说明题目大概率不是贪心，需要退回考虑动态规划、回溯、双指针等其它思路。

比如0-1背包问题，表面上是"按单位重量价值从高到低装"，但如果不允许拿部分物品，贪心会失败。构造一个容量10，物品A（重量6，价值6，单位价值1），物品B（重量5，价值4，单位价值0.8），物品C（重量5，价值4，单位价值0.8）。贪心先选A，剩余容量4装不下B或C，总价值6；最优是B+C总价值8。反例一秒钟就找到了。

4.4 与动态规划做一次"同题对比"

如果经历前三步后你还是拿不准，可以做一个对比：这题的暴力解法是不是会大量重复计算子问题？如果是，它可能更适合动态规划。而贪心只是动态规划的一个特例：每一步的"状态转移"被固定为最优选择，不需要枚举所有转移。我用一个表格记录自己常用的判断维度：

在实际刷题中，如果题目里出现"最多""最少""最大数量"这类词，我会把贪心、DP、二分、排序都放进候选，然后先用反例法把明显不行的排除掉。贪心不是万能的，但它确实是最快能验证的一类思路。

5. 贪心题目的代码骨架与三个常见坑

5.1 一套够用的代码模板

剥掉各种奇奇怪怪的题目背景，很多贪心题就是"排序 + 扫描 + 状态维护"。我总结了一套模板，可以覆盖大部分区间类、配对类贪心：

def greedy_template(items): # 1. 排序：选对排序维度 items.sort(key=lambda x: x[1]) # 比如按结束时间 ans = 0 current = None # 2. 扫描：边扫边做决策 for item in items: if acceptable(current, item): ans += 1 current = item return ans

这只是骨架，实际题目的"acceptable"逻辑差别很大。但骨架能提醒你：贪心的代码往往很短，真正的难度在排序维度和条件判断上。

5.2 三个debug到崩溃的常见坑

先说我踩过最多的坑：排序key选错。区间类题目，按左端点排序还是右端点排序，直接影响正确性。我只能用经验判断：如果目标是"数量最大化"，优先按结束时间排序；如果目标是"覆盖或合并所有范围"，优先按开始时间排序。两者混用会在示例通过、提交失败的边缘反复横跳。

第二个坑是状态更新顺序。比如跳跃游戏里，必须先把"是否可达"判断了，再更新max_reach。如果先更新max_reach再判断i > max_reach，会让本来不可达的位置被"未来能力"覆盖，导致错误判断。这也是很多贪心题目的通病：当前步只能使用截止到当前的信息，不能看到未来。

第三个坑是边界条件。加油站题里，如果循环里cur小于0就立即把start设为i+1，不要等循环结束；但total一定要在整个循环结束后判断。有些新手会在cur小于0时直接返回-1，这是错的，因为当前片段亏空不代表整个环路油不够。贪心题代码越短越要抠边界。

提示：如果一次提交没通过，不要急着改排序方向，先构造一个反例手算一遍。用纸笔推演比在编译器里瞎试快得多。

5.3 时间复杂度和优化空间

绝大多数贪心题的时间复杂度由排序主导，也就是O(n log n)。如果题目输入已经有序，可以做到O(n)。空间复杂度一般是O(1)或O(n)，取决于是否需要额外数组存diff、区间等。和动态规划相比，贪心最显著的优势是快、省空间。这也是面试官喜欢先问贪心的原因——如果能贪心，就不需要上DP那样重的武器。

6. 学完这一天，我对"弱智"和"算法"的重新认识

6.1 所谓弱智，其实是把复杂度留给思考

学完贪心这一天，我最大的感受是：一个看起来"弱智"的算法，恰恰是最需要动脑证明的算法。每一步选当前最优，听起来像不动脑子，但真正难的是判断"当前最优能不能通向全局最优"。这个判断不是靠背模板，而是靠问自己四个问题：子问题独立吗？局部最优能传导吗？能构造反例吗？和DP比更合适吗？这四个问题才是贪心的灵魂。

6.2 下一步该学什么

如果你也在按这个顺序学算法，我建议学完贪心后立刻去对比动态规划。尤其推荐"0-1背包""最长上升子序列"这类能同时用贪心和DP视角看的题，你会更快形成判断力。之后可以按热词里经常出现的顺序继续推进：剪枝算法（回溯优化）、KMP（字符串匹配）、归并排序（分治基础）、A*（启发式搜索）。贪心是这些算法里最简单也最容易误用的一块，把它真正吃透，后面学DP会顺畅很多。

6.3 学习贪心时我私藏的资料

最后分享几个我实际用过的资料，不吹不黑：

• LeetCode的贪心标签题单，按通过率排序刷前20道即可。
• 《算法导论》第16章，贪心算法与拟阵，学有余力再看拟阵部分。
• B站搜"贪心算法 正确性证明"，找有画图讲解的视频。
• 自己准备一个"反例笔记本"，把能推翻贪心的小用例记下来，比如[1,3,4]凑6、0-1背包的容量例子。面试前翻这个本子比重新刷题管用得多。

第23天的贪心之旅到这里就结束了。明天我打算用同样的"弱智"方式，去啃一啃动态规划，看看这两个经常一起出现的算法到底在哪些题上会打起来。