贪心算法从入门到进阶：原理、反例与刷题实战指南

今天是算法学习day27，主题锁定贪心算法。学到这里我发现一个有趣的现象：身边很多朋友一提起贪心，第一反应是"不就是每次选最大的嘛"，但真到做题的时候，要么想不出策略，要么想出来了却不敢写。这篇文章是我从day1刷到day27之后，对贪心算法的一次系统整理，包含原理、题型拆解、代码模板和踩坑记录，适合正在刷题、准备面试、或者刚学完基础数据结构想进阶的人参考。

1. 贪心算法不是"每次都选最大的"：本质与正确性门槛

1.1 先从一个"贪心会翻车"的例子说起

假设我们有面额为1、15、25的硬币，要凑出30块钱。如果按"每次拿最大的面额"这个思路走，你会先拿25，剩5，然后拿五枚1元，总共6枚硬币。但最优解明明是两枚15元，2枚硬币搞定。

这就是很多人对贪心的第一个误解：贪心不等于"每一步都拿最大/最快/最贵"。"每次都拿最大面额"只是贪心在特定场景下的一种表现，真正的贪心是——每一步都做出当前状态下的最优选择，并且相信这些局部最优选择拼起来就是全局最优。

在硬币面额为1、15、25的系统里，这种"每次拿最大"的策略显然不成立。而在我国常见的人民币找零场景里，因为面额设计特殊（1、5、10、20、50、100），贪心策略反而恰好总是对的。这说明什么？说明贪心能否成立，取决于问题本身的结构，而不是你贪不贪。

1.2 贪心成立的两个必要条件

要把贪心算法从"猜想"变成"可用的算法"，必须满足两个条件：

贪心选择性质：每一步的局部最优选择，最后能导向全局最优解。关键在于这个选择一旦做出，就不能反悔，也不需要回头修正前面的选择。

最优子结构：一个全局最优解，一定包含了子问题的最优解。也就是说，你先把第一步的最优选掉了，剩下的是一个规模更小的同类型问题，而你在这个子问题上继续用同样的贪心策略，仍然能拿到最优。

我自己的理解方式是：贪心像是爬一座"只有一个山头"的山。只要你每一步都朝最陡的方向爬，最终一定到山顶。但如果地形是连绵起伏的多峰结构，你朝最陡方向走，很容易被困在某个小山包上，这就是"局部最优不等于全局最优"。

动态规划之所以可靠，是因为它把所有可能的分支都记录下来，最后取最优。贪心不做穷举，它只走一条路，所以必须有一条"这条路一定通向全局最优"的保证。这种保证不能靠感觉，要有证明。

1.3 证明贪心正确性的两种常用套路

面试和竞赛中，最常见的证明方法有两种：

交换论证法。假设某个最优解和贪心选择不同，那我尝试把这个最优解里的某个元素和贪心选择的元素交换一下。如果交换之后解不会变差，就说明贪心选择的元素完全有资格出现在某个最优解里。反复做这种交换，就能把一个任意最优解"变"成贪心解。区间调度类题目经常用这个方法。

数学归纳法。证明第i步贪心选择之后，剩余子问题仍然保留最优性质，然后归纳到整个问题。

不过说实话，日常刷题很少真的要写完整证明。我自己的做法是：先用小规模例子验证，再用反例思维去攻击这个策略——如果我能构造出一个反例，说明贪心不成立；如果构造不出来，而且直觉和常见结论都支持，那就大概率可以写。

2. 从最"无脑"的三道题建立手感：分发饼干、柠檬水找零、最大子数组和

2.1 分发饼干：排序后双指针，喂"最不浪费"的那个

题目场景很朴素：有一群孩子，每个人的胃口值不同；有一堆饼干，每块饼干的大小不同。一块饼干只能喂一个胃口小于等于它大小的孩子，问最多能满足几个孩子。

我第一眼看到这个题，脑子里冒出的策略就是：小饼干喂小胃口。为什么不是大饼干喂大胃口？因为如果我把大饼干拿去喂了胃口小的孩子，那胃口大的孩子可能就没饼干吃了；反过来，小饼干本来也喂不了大胃口的孩子，所以它唯一的用处就是喂尽量小的胃口。这个"最小浪费"思路就是贪心选择性质。

实现上很简单，排序之后两个指针一起走：

int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i = 0, j = 0; while (i < g.size() && j < s.size()) { if (s[j] >= g[i]) { i++; // 满足一个孩子 } j++; // 无论是否满足，饼干都要往后走 } return i; }

复杂度是O(n log n)，瓶颈在排序。这道题让我意识到，贪心题往往第一步是排序——排序让"当前最优"变得可计算。如果不排序，你无法确定哪个饼干是"恰好够用"的。

2.2 柠檬水找零：唯一正确的动作是"大票优先找零"

这道题说的是卖柠檬水，一杯5块钱。顾客排着队来买，可能给5元、10元、20元，你要保证每个人都能正确找零，初始时你手头一分钱没有，判断能不能给所有顾客找开。

这题的贪心策略藏在一个特别朴素的地方：收到10元时，你只能找一张5元；收到20元时，你有两种找法，一种是一张10加一张5，另一种是三张5。应该优先用10元去凑20的找零，因为5元是"万能小钞"，10元只能在找20时才用到，一旦你用掉三张5，后面来了一个10元，你可能就找不开了。

bool lemonadeChange(vector<int>& bills) { int five = 0, ten = 0; for (int b : bills) { if (b == 5) five++; else if (b == 10) { if (five == 0) return false; five--; ten++; } else { // 20 if (ten > 0 && five > 0) { ten--; five--; } else if (five >= 3) { five -= 3; } else { return false; } } } return true; }

注意这里有一个隐藏的坑：有人会觉得，收到20元时如果手里有10元，可以先把10元留着，"万一后面还有人给20呢"。实际上这是反的——你这次找零都过不去的话，后面根本没有"万一"。贪心算法的特点是只关心"当下能不能过"，因为每一步都是当前状态下的最优决策，而这题恰恰证明了：优先用10元是当前状态下最不消耗稀缺资源的选择。

2.3 最大子数组和：你分不清它是DP还是贪心

给定一个整数数组，找出一个具有最大和的连续子数组。这题最著名的解法是Kadane算法，核心就一行：

int maxSubArray(vector<int>& nums) { int cur = 0, best = INT_MIN; for (int x : nums) { cur = max(x, cur + x); best = max(best, cur); } return best; }

这个式子的贪心解释特别漂亮：一旦当前的累加和cur变成负数，它对后面任何位置的贡献都是负的，所以果断把它丢掉，从当前元素重新开始累加。负数像一段糟糕的关系，及时止损才是最优。

但有意思的是，这道题也经常被归为动态规划，因为cur本质上是一个状态，转移方程是dp[i] = max(nums[i], dp[i-1] + nums[i])。它其实是"贪心思想和DP状态表示恰好重叠"的那类题。这类题给了我一个很重要的启示：算法分类不是死板的，关键是看透题目的结构，而不是纠结标签。

3. 移动类贪心：跳跃游戏、加油站和"可达范围"

3.1 跳跃游戏：维护每步能走到的最远位置

题目：给定一个非负整数数组，每个数字代表你在当前位置最多能往后跳几步，初始在下标0，判断能否到达最后一个下标。

这个题如果走"每次跳最远"的思路，反而容易错。举个反例：数组是[3, 4, 1, 0, 0, 1, 1]。从下标0按"跳最远"的贪心会跳到3，而下标3是0，直接卡死；但最优路径是先跳到1，再一路跳到终点。这说明"看起来最贪心"的动作不一定是最优的。

正确的贪心策略是：维护一个"当前能到达的最远下标"maxReach，遍历过程中不断用它覆盖到的位置去更新它。你不需要决策具体跳到哪里，只需要知道"这一步能覆盖的范围有多大"。

bool canJump(vector<int>& nums) { int maxReach = 0; for (int i = 0; i < nums.size(); i++) { if (i > maxReach) return false; // 这个位置根本到不了 maxReach = max(maxReach, i + nums[i]); if (maxReach >= nums.size() - 1) return true; } return true; }

为什么这样是贪心？因为maxReach是遍历到当前位置时能到达的最远位置，我们每次都选择更新到最大，相当于把"可达范围"这个状态最大化。只要这个最大范围没有断档，就一定存在一条路径走到范围内任何一点。这是"覆盖范围最大化"型贪心，重点是范围而不是具体落点。

3.2 跳跃游戏II：最少跳数里的"区间分段"思想

进阶版是在保证能到达终点的前提下，求最少跳数。我一开始想的贪心是"每次跳到能跳最远的位置"，又被反例教育了。正确的思路是按"一步能覆盖的区间"来切分：

遍历当前步覆盖的区间[i, end]，期间不断记录下一步能达到的最远位置maxPos。当遍历到end时，说明这步覆盖区间的所有位置都已经处理完，必须跳一步，于是end = maxPos，步数加一。

int jump(vector<int>& nums) { int steps = 0, end = 0, maxPos = 0; for (int i = 0; i < nums.size() - 1; i++) { maxPos = max(maxPos, i + nums[i]); if (i == end) { end = maxPos; steps++; } } return steps; }

这个解法的精妙之处在于：你并没有真的模拟"跳到了哪"，而是把每一步看作一次"区间推进"。当前区间能覆盖到的所有点，都是这一步可以落脚的候选点，而下一步区间是这些候选点能延伸到的并集。每走完一个区间，必然需要消耗一步。这就是典型的"过程最优"贪心。

3.3 加油站：先判断全局可行性，再找唯一起点

沿环路上有若干个加油站，每个站能加油，每段路要消耗油，问从哪个站出发能绕一整圈回到起点。

这题的贪心策略非常经典。先对整个数组求total = sum(gas[i] - cost[i])，如果total < 0，说明总油量都不够总消耗，无论从哪出发都不可能。接下来用curSum记录从候选起点开始的累积剩余油量，一旦curSum < 0，就把起点设置为i + 1并把curSum归零。

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int total = 0, curSum = 0, start = 0; for (int i = 0; i < gas.size(); i++) { total += gas[i] - cost[i]; curSum += gas[i] - cost[i]; if (curSum < 0) { start = i + 1; curSum = 0; } } return total >= 0 ? start : -1; }

为什么要在这个位置重置起点？逻辑是这样的：假设从start出发，走到i时累积油量变负了，那就说明从start到i之间的任意一个加油站k作为起点，都不可能越过i这个位置。因为从k出发到i时，油量只会更少——你等于把start到k这一段本来就没攒下的油给跳过了，剩余积累不可能比从start出发更多。所以唯一值得尝试的新起点就只能是i+1。这个"累积和为负就重置"的思路，在很多前缀和、差分相关的问题里都能看到。

4. 区间问题专项：排序决策是贪心的主战场

4.1 无重叠区间：为什么必须按结束时间排序

题目是：给定一个区间的集合，求最少需要移除多少个区间，才能让剩下的区间互不重叠。

大多数第一次做区间题的人，第一反应是按start排序。然后你会构造出一个反例：区间A是[1, 100]，区间B是[2, 3]，区间C是[3, 4]。如果按start排序，你会先看到A，然后B、C全都被A盖住，判断结果为只能保留1个区间；但正确答案是保留B和C，移除A，答案是移除1个。

正确的贪心策略是：按end升序排序，优先保留结束最早的区间。理由用交换论证很容易说明：在所有互不重叠的最优方案里，如果把第一个区间换成所有区间里end最小的那个，后面的区间也不会被这个新区间挡住，因为新区间的结束时间不晚于原来那个。这就是"结束最早的区间给后面留下了最大空间"。

int eraseOverlapIntervals(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[1] < b[1]; }); int count = 1; int lastEnd = intervals[0][1]; for (int i = 1; i < intervals.size(); i++) { if (intervals[i][0] >= lastEnd) { count++; lastEnd = intervals[i][1]; } } return intervals.size() - count; }

做题时我发现一个关键词规律：看到"最少移除""最多保留""最多能安排"这类字眼，基本就是贪心区间题。这类题排序键的选择是生死线——排错一个键，整个算法就废了。

4.2 合并区间、引爆气球：排序键怎么选

合并区间这题是按start排序，然后检查当前区间是否和前一个合并结果重叠，重叠就扩展end，不重叠就开启新区间。它有时候被划进贪心，但我觉得它更像是"排序加扫描"，因为每一步并没有"做选择"，只是在如实合并。

真正值得对比的是"用最少的箭引爆气球"这类题：在二维平面里，多个区间（气球）如果共享某个x坐标，就能被同一支箭引爆，求最少箭数。这题其实是无重叠区间问题的镜像，同样按end排序，然后计数：只要当前气球左端不超过当前箭的x坐标（也就是之前保留区间的end），就可以共用一支箭；否则必须新开一支箭并更新位置。

这些题的共性套路非常清晰：

• 第一步：明确排序键，到底按start还是按end，取决于你希望"留下谁"。
• 第二步：维护当前合并/保留区间的右端点。
• 第三步：遇到重叠做决策，不重叠就重置。

4.3 区间类贪心的本质：一维上的资源分配

不管是会议安排、课程表排课、最少箭矢，还是无重叠区间，本质都是"在一条时间线上尽可能多地安排互不冲突的事件"。这类问题的标准答案是：每次选结束最早的那个事件。这个结论可以追溯到活动安排问题，几乎是贪心算法教科书里最经典的模型。

我个人的经验是，碰到区间题先不要急着写代码，先在纸上画出几个区间，用排序键不同的方案各跑一遍，哪个能通过最极端的情况，哪个就是对的。区间题是最容易通过画图发现反例的题型，一定要利用这个优势。

5. 贪心和动态规划怎么选：day27之前我踩过的识别坑

5.1 关键差别：做完选择之后，需不需要回头看

我前二十多天动态规划刷得比较多，所以学贪心的时候一直在想：什么题该用DP，什么题该用贪心？后来总结出一个特别直接的口头标准：如果这一步做了选择，后续不需要因为未来信息而修改这个选择，那大概率可以贪心；如果当前选择会限制未来的可能性，那就要DP。

我做了一个对比表，方便你考前复习：

这个表是给别人看的，我自己判断时只问一个问题："全局最优 = 每一步都局部最优"这个等式成立吗？成立就是贪心，不成立就是DP，或者至少需要更复杂的手段。

5.2 最经典的对比：0-1背包和分数背包

同样是背包问题，0-1背包（物品不可分割）通常要DP，分数背包（物品可以切任意大小）用贪心就拿单位价值最高的先装。差别就一个：可不可分割。

为什么不可分割时贪心会错？因为一个体积大、单位价值高的物品，可能占用大量空间，导致你装不下几个小物品，最后总价值反而不如配合小物品的组合。分数背包里没有这个问题，因为剩下的空间理论上总能被切碎的物品填满，单位价值高的物品优先自然最优。

我刷题时经常用这道对比题当"分水岭"：能一眼说出这两者的区别，就说明你理解贪心的边界了。

5.3 股票买卖系列：同一个场景三种算法

股票买卖的题目同样能说明这个问题：

• 只买卖一次（求最大一次差价）：维护历史最低价，当前价格减去历史最低价就是当前卖出的利润，取最大值。这一步天然是贪心。
• 可以买卖多次：把每一段上涨的利润都累加起来，只要prices[i] > prices[i-1]就赚这一段。这是贪心的"吃掉所有正收益"思路。
• 最多买卖两次：这就要DP了，因为第二次交易依赖于第一次交易的结果，当前决策会影响后续机会。

同一个背景，稍微改动限制条件，算法就完全不同。这也是为什么我不建议死背题，而是要在做题时主动追问"这个限制条件改变了什么"。

5.4 我的判别流程（可复用的思考路径）

我现在拿到一道题，会按以下顺序快速过一遍：

1. 读题后先问：题目求的是"最多/最少/最大/最小"吗？如果不是，贪心的概率下降。
2. 自己尝试给出一个"当前状态下的最优动作"，比如排序后取最小的、覆盖范围最远的、结束时间最早的。
3. 立刻尝试构造反例。如果构造不出来，把策略写下来；如果很快构造出反例，就放弃贪心。
4. 写代码时先写暴力/DP版跑小数据，用随机数据对拍。这一步能挡掉大部分假贪心。
5. 如果对拍通过，再反推一遍"为什么这个策略成立"，确保不是碰巧。

这套流程让我在day27之后基本告别了"贪心写了个寂寞"的窘境。

6. 贪心刷题中的常见反例与个人检验方法

6.1 三个让我差点翻车的反例

反例一：特殊面额找零。前面已经说过，面额是1、15、25时，凑30用"每步取最大"会拿到6枚硬币，而最优是2枚。它的教训是：贪心的成立依赖面额结构，不能把一个场景里的成功经验盲目迁移到另一个场景。

反例二：跳跃游戏"每次跳最远"策略。数组[3, 4, 1, 0, 0, 1, 1]里，索引0能跳到3、1、2，其中3最远但值为0，跳过去就死；跳到1才是正解。这说明"当前步最远"不等于"全局可达最优位置"。正确贪心必须维护一个覆盖范围，而不是定格在某一个跳跃点。

反例三：区间问题按start排序贪心。区间A[1,100]、区间B[2,3]、区间C[3,4]，按start排序先选A，只能得到1个区间，最优却是B和C两个。这说明区间题的排序键决定一切。

我把这三个反例贴在笔记首页，每次写贪心之前先看一眼，提醒自己三个口诀：看面额结构、看覆盖范围、看排序键。

6.2 验证一个贪心策略是否为真的三条经验

经验一，一定要对拍。我大部分贪心翻车都是靠暴力解法对拍揪出来的。你不需要用大样本，每组几百个随机小数据就够了，一旦出现不一致，立刻能定位错误策略。

经验二，从"交换论证"的角度自问。如果我的贪心解和某个最优解不同，能不能把这个最优解里的元素和我的贪心元素交换，并且结果不变差？如果答案是肯定的，说明策略有戏；如果交换后明显变差，那基本就是假贪心。

经验三，注意那些"排序一次+扫描一遍"的问题。这类题的错误往往不是扫描逻辑，而是排序键。我会把"按start排"和"按end排"各跑一遍测试数据，用实际输出说话。

6.3 day27之后的贪心学习路线

如果今天这篇内容你全部吃透了，下一步可以按这个顺序继续：

• 第一梯队（打基础）：分发饼干、柠檬水找零、买卖股票2、最大子数组和。这些题代码短、陷阱少，适合建立"贪心=局部最优决策"的直觉。
• 第二梯队（练思维）：跳跃游戏1和2、加油站、无重叠区间、用最少箭矢引爆气球。它们核心都是"范围/排序"，是面试高频。
• 第三梯队（挑战边界）：摆动序列、单调递增的数字、监控二叉树。这类题需要更强的推导能力，尤其是监控二叉树这种在树上做贪心的，能彻底检验你是否真的理解了贪心的适用条件。

刷题节奏上，我建议贪心这部分每天三到五题，不要贪多。贪心题的代码往往很短，但每一道都要能说清楚三步：为什么排序？为什么选这个键？为什么这个局部决策不影响全局。能把这三句话说明白，才是真的会了。

最后说点我自己的体会

学了27天，最大的感受是贪心算法是所有非暴力算法里"看起来最容易、实际上最需要严谨"的一种。它不像动态规划那样状态一目了然，也不像回溯那样有模板可套，它的难点全在一个"为什么"上。所以我现在每做完一道贪心题，都会强制自己在注释里写一行"贪心依据"，写不出来就再回头想。这个习惯让我翻车次数少了很多。

如果你正在学习算法，也建议你把今天讲的反例记下来，在自己想当然的时候拿出来泼一盆冷水。贪心算法真的不难，难的是永远对"局部最优"保持警惕。