贪心算法刷题指南：从局部最优到全局最优的实战套路

刷LeetCode刷到一定阶段贪心算法是绕不开的一道坎。很多人一看到“贪心”两个字就觉得玄乎好像全靠直觉和碰运气其实不是这样。我在刷了两百多道题之后对这类题型的感受是贪心确实吃思路但思路背后是有固定套路和判断标准的题做多了你会发现它甚至比动态规划更容易“有迹可循”。这篇文章我挑了几道非常典型的贪心题目从“为什么这么想”到“代码怎么写”再到“哪些坑我踩过”一步步拆开讲。适合正在刷题准备面试的人也适合刚学算法、想搞懂贪心本质的学生。我会尽量用大白话把每道题的思维过程还原出来而不是只贴一套标准答案。1. 贪心算法的适用场景与思考框架1.1 贪心的本质局部最优如何推导全局最优贪心算法的核心思想其实一句话就能说完每一步都做出当前看起来最好的选择并寄希望于这些局部最优能叠加成全局最优。这个思路在我们生活中也到处都有。比如你去自助餐厅盘子只有那么大你是先把最贵的菜装满盘子还是先绕场一周看看都有什么再决定贪心策略就是“直接拿最贵的”因为它假设最贵的菜就是最好的选择。但问题来了这个假设并不总是成立。如果自助餐厅最贵的菜是龙虾但龙虾旁边就是帝王蟹你盘子满了之后才发现没肚子吃帝王蟹了这时候你还会觉得“拿最贵”这个策略正确吗算法题里的贪心失效本质上是同一个道理——局部最优不一定能推出全局最优。所以判断一道题能不能用贪心最核心的问题不是“这个选择看起来好不好”而是“这个选择会不会堵死后续更优的路径”。如果你能证明“当前做出的最优选择仍然包含在某个全局最优解里”那么贪心就是成立的。这种证明方式通常叫交换论证——假设最优解和贪心解在某个位置不同通过交换操作证明贪心解不会比最优解差。1.2 贪心题型的几种常见模型刷了那么多题之后我总结出贪心题目常见的几类场景基本上能覆盖大部分题目排序配对型先排序再用双指针或逐个匹配解决问题比如后面要讲的分发饼干。覆盖型维护一个当前能覆盖的范围每次贪心地扩大这个范围比如跳跃游戏。区间调度型一堆区间让你选择或处理关键往往在于按什么规则排序比如无重叠区间。环形资源型题目给了一个环形的结构需要找到合适的起点或分配方式比如加油站。双向扫描型一次方向扫描不够需要正反各跑一遍才能同时满足约束比如分发糖果。这些模型不是孤立的很多题目是混合体。有了这个框架你看到一道新题时就能先在脑子里对上号这题到底属于哪一类用哪种贪心策略最自然我个人的经验是先判断命题里的“局部最优”是否清晰。如果一道题的“当前最优选择”很直观且你很难举出反例来推翻它那大概率就是贪心题。反过来如果直觉告诉你“当前选了最优后面可能会出问题”那就得考虑动态规划或者其他解法了。关于贪心失效的更多细节我会在第7章专门讲。2. 分发饼干最基础的排序双指针贪心2.1 题目分析与贪心策略题目是这样有一群孩子每个孩子有饥饿度还有一堆饼干每块饼干有尺寸。一块饼干分给一个孩子条件是饼干的尺寸要大于等于孩子的饥饿度。问最多能喂饱几个孩子这是贪心入门最经典的一道题没有之一。最容易想到的策略有两种。一是把最大的饼干给最贪吃饥饿度最大的孩子让他吃饱然后剩下的饼干继续这样匹配。二是把最小的饼干给饥饿度最小的孩子能喂就喂不能喂就换更大的饼干。两种策略看起来都可以但实现上有差别。第二种更好写。为什么因为把最小饼干给最小胃口的孩子如果这块最小的饼干都不能满足他那这块饼干就对任何孩子都没用了——毕竟比他还饿的孩子吃不了更大的饼干但也没必要用大饼干去满足小胃口。反而是跳过大饼干不浪费直接看下一块更大的饼干。这句话我再展开一下因为很多人没绕过来这个弯。当前最饿的孩子和孩子种最小胃口的逻辑关系是如果“最小的饼干满足不了最不饿的孩子”那么这个饼干对所有人都没用了直接丢弃如果能满足就把这块饼干分给他因为这是“用最少的资源解决最容易满足的需求”。2.2 代码实现与复杂度分析理解了策略代码其实非常简单。我先把代码贴出来然后再讲细节int findContentChildren(vectorint g, vectorint 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; }这里有两个边界点需要特别注意。第一while循环退出条件是两个数组任意一个遍历完。如果孩子先遍历完说明所有能被满足的孩子都喂饱了直接返回 i 即可。如果饼干先遍历完说明已经没有饼干能用剩下的孩子即使再饿也没办法了。第二j放在 if 外面这点很关键——它保证饼干永远在推进而孩子只有在被满足时才推进。时间复杂度是排序的 O(nlogn)空间复杂度取决于排序算法是原地还是非原地的通常算 O(1)。2.3 这道题给我的经验这是贪心题目里最经典的一道“无后效性”问题。我做这道题时的最大感悟是贪心策略的选择直接决定了代码的复杂度。如果你选了“最大饼干给最饿的孩子”代码也差不多但思维上更容易绕进“这个孩子能不能吃小一点的饼干”的纠缠里。而“最小饼干给最小胃口”天然自带了一种“不行就换下一块”的冷漠逻辑适合写成循环结构。我见过很多人在这道题上纠结如果孩子胃口是 [1,2,3]饼干是 [1,1]到底该怎么分按贪心逻辑最小的饼干 1 给胃口 1 的孩子下一个饼干 1 给胃口 2 的孩子不够。所以结果是 1。但如果你先拿胃口 3 和饼干 1 比会觉得“这也差太远了”。这就说明你选择的贪心顺序会影响你的思考成本。选对了贪心方向代码量直接减半。3. 跳跃游戏与跳跃游戏II覆盖范围型贪心3.1 跳跃游戏怎么判断能否到达终点题目是给一个非负整数数组每个元素代表你在该位置最多能跳多远起点在第一个位置问能否跳到最后一个位置。这道题我刚看到时第一反应是想用动态规划——用 dp[i] 记录能不能到位置 i。但后来发现完全没必要贪心就够了。思路是维护一个当前能到达的最远位置遍历过程中不断更新它。只要在遍历过程中当前位置没有超过最远可达位置就说明当前这点是能到的可以用它的跳跃力去扩展最远位置。如果某个时刻当前位置已经大于最远可达位置说明后面都到不了了。代码bool canJump(vectorint nums) { int maxReach 0; // 当前能到达的最远下标 for (int i 0; i nums.size(); i) { if (i maxReach) return false; maxReach max(maxReach, i nums[i]); } return true; }有个细节这里对 nums 的遍历是完整的但循环里每次都检查i maxReach。如果已经走不到某个位置直接返回 false。这背后的贪心选择是什么就是每次更新 maxReach 时取能跳到的最远位置。为什么不需要选择“跳哪个点”因为题目只问“能不能到”没让你求最小步数所以只需要关注可覆盖范围的扩展不需要关注具体路径。3.2 跳跃游戏II如何用最少步数跳到终点这题是上一题的进阶版题目保证能到达终点问最少跳跃次数。我一开始想的是 BFS 或者动态规划但看了贪心解法的实现之后发现思路特别干净。核心在于要维护两个变量当前这一跳能到的边界end以及从当前位置出发在边界内所有点能到达的最远位置farthest。当遍历到边界时说明这一步的“势力范围”已经搜索完了必须跳一步更新边界为farthest。int jump(vectorint nums) { int jumps 0, end 0, farthest 0; for (int i 0; i nums.size() - 1; i) { farthest max(farthest, i nums[i]); if (i end) { jumps; end farthest; } } return jumps; }这里的最核心之处在倒数第二行的循环条件i nums.size() - 1不是i nums.size()。因为当到达最后位置时不需要再跳了否则会在终点跳一次多余步数。我第一次提交就踩了这个坑测试用例画蛇添足地多跳了一次去查才发现是边界问题。3.3 覆盖型贪心的通用套路这两道题放在一起看能看出覆盖型贪心的通用套路用一个变量记录“当前可控范围”遍历时不断扩展这个范围当需要决策时比如本题的跳跃次数才依据这个范围做出选择。很多人会误以为跳跃游戏II的贪心是“每次跳得最远就对了”。实际上不是。反例很容易构造比如 [2, 3, 1, 1, 4]第一个位置能跳 2 步如果直接跳到最远的 index 2值为 1那还要再跳两次但如果你跳到 index 1值为 3下一步就能直接到终点。这说明局部最远不等于全局最优。正确的贪心是“在下一步可达的范围内选能让下下步范围最大的位置”这就是前面说的“更新边界为 farthest”的原因。4. 无重叠区间与最少箭矢区间调度类贪心的核心4.1 无重叠区间按右端点排序为什么是对的题目是给定一个区间的集合求需要移除区间的最小数量使剩余区间互不重叠。这是区间调度类题目的祖宗。开头的关键选择是按左端点排序还是按右端点排序这直接决定了解法复杂度。我第一次做的时候按左端点排序然后逐个判断重叠发现边界情况特别多写了一堆 if-else 还是过不了所有用例。后来才明白区间调度问题里按右端点排序才是贪心最优的通用做法。原因不复杂按右端点从小到大排序后当前区间结束得越早留给后面区间的空间就越大。我们需要“保留尽量多的不重叠区间”所以选择的策略应该是“优先保留结束早的区间”。如果按左端点排当前区间结束得稍微晚一点就可能挤掉后面好几个本可以装下的区间。按右端点排序后遍历时只需记录一个end值每当新区间的左边比 end 小就说明有重叠需要移除当前区间否则就是无重叠的。4.2 最少箭矢一道反过来的区间题最少箭矢这道题是在二维平面上有一堆气球每个气球占据水平方向的区间 [x_start, x_end]弓箭可以从某个 x 坐标垂直射上去只要射中气球的 x 区间就算射破。问最少几箭可以射破所有气球。这题粗看和无重叠区间很像但思考方向反过来了无重叠区间是“去掉重叠的”这题是“把重叠的射破”。但本质上是一样的——如果一堆气球区间有公共交集那么一支箭就可以射破它们。所以最少箭数就是最少需要多少个“不重叠的区间组”每个组内区间两两有交集。求解思路还是按右端点排序维护当前组的最右边界遍历时如果当前气球左边界大于当前边界就需要多一支箭并更新边界为当前气球的右端点。int findMinArrowShots(vectorvectorint points) { sort(points.begin(), points.end(), [](auto a, auto b) { return a[1] b[1]; }); int arrows 1, end points[0][1]; for (int i 1; i points.size(); i) { if (points[i][0] end) { arrows; end points[i][1]; } } return arrows; }这里有个容易写错的点判断条件里是而不是。因为气球区间如果端点相同也算能重叠一支箭可以同时射破两个端点重合的气球。如果用会把边界情况算成不重叠导致箭数多出。做这题的时候我用交了一次发现多射了两箭改回就对了。4.3 区间类题目速查题型排序基准核心操作无重叠区间右端点升序记录 end重叠时移除当前区间最少箭矢右端点升序记录 end左端点 end 时新增箭合并区间左端点升序依次合并相交区间插入区间左端点升序找到插入位置合并相交部分这些题其实在问同一个问题这个集合里最多能选出多少个互不相交的区间而这个问题的答案就是经典的最大不相交子区间数量按结束时间贪心即可。5. 加油站环形结构下的贪心起点搜索5.1 题目描述与暴力的局限加油站这题在很多公司面试里出现的频率挺高。题目给两个数组gas[i]表示第 i 个加油站能加的油量cost[i]表示从第 i 个加油站开到第 i1 个加油站的耗油量。车是环形行驶的油箱容量无限问从哪个加油站出发能绕一圈回到起点如果不存返回 -1。题目保证只有唯一一个答案或者没有答案。暴力做法是枚举每个起点模拟一圈复杂度 O(n²)。但题目给的数据量不大时还能过数据量一大就超时了。贪心的关键洞察是如果从某个点出发累积油量在某一步之前变成了负数说明从这段路径内任何一个点出发都不可能完成整个环。因为你在中间任何一个点起步时拥有的初始油量是 0反而比从头带过来的累计剩余油量要少更不可能走完这段路。所以正确做法很简单先判断总油量是否小于总消耗小于则无解否则从某个起点开始跑一旦累积油量为负就换下一个点为起点继续尝试。5.2 贪心优化后的代码实现int canCompleteCircuit(vectorint gas, vectorint cost) { int total 0, cur 0, start 0; for (int i 0; i gas.size(); i) { total gas[i] - cost[i]; cur gas[i] - cost[i]; if (cur 0) { start i 1; cur 0; } } return total 0 ? -1 : start; }这里total用来判断整体是否能跑完cur用来在当前起点下追踪剩余油量。一旦cur 0就说明起点start不行直接换到i1。为什么敢这么换因为如果从 start 到 i 这段的累积净油量为负那你从这段里的任何一点出发初始都是 0 甚至更少根本不可能跳过这个“负积累区间”。只有从 i1 之后重新开始才可能通过。5.3 这道题的“上帝视角”理解我看过很多人的题解都在讲“负区间就换起点”但没人解释为什么搜一遍就够。我后来想明白一个类比这段环形路就像跑接力赛。你可以把整个路径看成若干段每一段出发时若初始油量为 0跑到某一点油量变成负就说明这一段没有一个点能当合法起点。等到下一段开始再重新累计。因为总油量大于等于总消耗所以最后一定能找到某个点“攒够”油量走完剩下的路。这个逻辑我在代码里反复验证过确实是 O(n) 的一次遍历搞定。面试时候如果能把这段“为什么会换起点”讲清楚面试官通常会满意。6. 分发糖果经典的双向扫描边界贪心6.1 为什么一次遍历不够需要两个方向分发糖果这题题目大家肯定不陌生一堆孩子站成一排每个孩子有一个评分你需要给每个孩子至少一颗糖果同时满足两个条件相邻的孩子里评分高的必须得到比评分低的更多的糖果。问最少需要多少颗糖果。这个题第一眼看起来像个从左到右的简单比较如果右边评分高就给右边多发一颗。但试过就会发现问题。如果评分是 [1, 2, 3, 2, 1]从左到右扫完变成 [1, 2, 3, 1, 1]但这样位置 3评分2和位置 4评分1是不是满足“评分高的糖果多”位置 3 的孩子评分 2 比位置 4 的孩子评分 1 高但他们的糖果数都是 1这就违规了。问题出在一次从左到右只能保证“每个孩子和左边的邻居比较时满足条件”但不能保证“和右边的邻居比较时也满足条件”。所以必须再加一次从右到左的扫描保证每个孩子同时满足两个方向上的约束。6.2 双向扫描的代码实现与易错点int candy(vectorint ratings) { int n ratings.size(); vectorint candies(n, 1); for (int i 1; i n; i) { if (ratings[i] ratings[i-1]) { candies[i] candies[i-1] 1; } } for (int i n - 2; i 0; i--) { if (ratings[i] ratings[i1]) { candies[i] max(candies[i], candies[i1] 1); } } return accumulate(candies.begin(), candies.end(), 0); }最关键的代码就是第二次扫描里的max(candies[i], candies[i1] 1)而不是直接赋值candies[i] candies[i1] 1。为什么不能直接赋值因为第一次扫描已经保证了左方向的约束用一个较大的值覆盖掉会破坏掉左方向的满足性。正确的做法是取两者较大的既能满足左约束又能满足右约束。这是我做这道题踩过最大的坑当初直接赋值案例通过率一直是红的。6.3 这道题对贪心的启发多个约束条件可能要多方向扫描分发糖果这道题我印象很深因为它不是什么“排序贪心”或“覆盖贪心”而是贪心对局部约束的拆解。一个约束拆成两个方向的扫描每个方向只满足一半合起来就是完整解。以后遇到类似“两边同时比较”的题——比如接雨水——你就该意识到多半要先从左往右处理一遍再从右往左处理一遍最后把结果合并。7. 贪心失效的场景与排查方法7.1 哪些情况下贪心不成立很多人把贪心算法当成万能药看到“最优解”就往上套。但贪心最大的陷阱就是它看起来太自然了以至于你很难察觉它在某些场景下会失效。最常见的失效场景有两种。第一种局部最优选择会导致后来的状态变化使得原本不优的选择变成更优。经典例子是 0-1 背包问题。假设背包容量固定每件物品只能整件拿走如果你按单位重量价值从高到低贪心地拿最后背包可能剩下一小块空间只能浪费。但如果先装一个单位重量价值不是最高、体积更适配的物品反而可能拿到总价值更大的组合。这个场景就是典型的局部最优和全局最优脱节。第二种当前的最优选择会修改未来的可选集合导致未来的最优不可达。比如找零钱问题如果硬币面额是 [10, 7, 1]要凑 15 块钱贪心会先拿一个 10再拿五个 1总数是 6 枚。但实际上 771 只需要 3 枚。这个场景里“尽量用大面额”看似没错但因为 10 的倍数和 7 之间没有整除关系贪心策略直接漏掉了最优组合。所以做题遇到“背包类”“凑数类”“需要组合选择”的题目时第一反应不应该是贪心而应该是动态规划或者回溯。怎么快速判断有个很实用的经验法则如果你给一串数据能很轻松构造出反例推翻贪心策略那基本说明这题不是贪心题。反之你尝试很多用例都满足才有继续用贪心的价值。7.2 贪心失效的快速排查清单我总结了一个排查清单遇到疑似贪心题但不敢确认时逐个过一遍[ ] 当前选择会不会影响未来的可选集合会的话慎用贪心。[ ] 是否存在“空间浪费”型的成本比如背包里的剩余容量。[ ] 是否要求的是“最少个数”“最短路径”而不是“最大价值”通常后者贪心更危险。[ ] 能不能构造反例用“极端值”和“边界值”拼一组数据测试。[ ] 问题是否有“无后效性”也就是当前选择之后后面问题的性质不应该发生变化。我自己的经验是如果一道题你纠结了 20 分钟还没办法证明贪心成立那就直接去试动态规划。不要在一棵树上吊死面试的时间消耗不起。8. 掌握贪心后如何举一反三8.1 从具体题目抽象出模式前面讲的这些题表面看各不相同实际上都能归到有限的几个模式里。分发饼干是“排序配对”跳跃游戏是“覆盖范围”无重叠区间是“区间调度”加油站是“环状资源分配”分发糖果是“双向约束”。我建议你刷题时不要只刷不总结每做完一道题把它的模式记下来旁边标注“当前选择是否影响后续选择”。以后遇到新题先匹配模式再验证无后效性很快就知道能不能用贪心。这一点是我刷题后段位提升最快的时期的关键不是多刷题而是多总结模式。8.2 刷题顺序与时间安排的建议如果你想系统地练贪心我建议按以下顺序刷分发饼干455、柠檬水找零860基础排序配对建立信心。跳跃游戏55、跳跃游戏II45覆盖型贪心的两个变体理解“最远覆盖”思维。无重叠区间435、用最少数量的箭引爆气球452区间类贪心理解为什么按右端点排序。加油站134、分发糖果135进阶题目开始涉及环形结构和双向约束。合并区间56、最大数179把贪心思维结合排序与比较器。每组刷完后给自己 10 分钟不看题解口头复述每道题的贪心策略和证明思路。这个过程不只是在复习题是在强化“判断能否用贪心”的直觉对面试特别有帮助。9. 再做几个变体加深理解9.1 区间合并与插入区间前面提到了合并区间和插入区间其实它们也可以从贪心角度理解。合并区间的思路是先按左端点从小到大排序然后从左到右扫描维护当前合并区间的左右端点。如果当前区间与合并区间有交集当前区间左端点 当前右端点就更新右端点否则把当前合区间推入答案开始一个新的合并区间。vectorvectorint merge(vectorvectorint intervals) { sort(intervals.begin(), intervals.end()); vectorvectorint res; for (auto interval : intervals) { if (res.empty() || res.back()[1] interval[0]) { res.push_back(interval); } else { res.back()[1] max(res.back()[1], interval[1]); } } return res; }插入区间则是利用有序性质找到合适的插入位置后用和合并区间相同的方式进行合并。这两题虽然不难但和前面的区间题结合起来会让你对“区间问题先排序再看重叠”这套打法印象更深。9.2 最大数特殊排序规则下的贪心最后一题是最大数。这题本质虽然是排序但对理解和训练贪心思维也非常有好处。题目是给定一堆非负整数把它们排成一个最大的数。比如 [3, 30, 34, 5, 9]最大排列是 9534330。难点在于数字的比较关系不是普通数值比较而是字符串形式的比较。你要自己定义一个比较器比较 ab 和 ba 两个拼接结果谁更大。这个比较器是完备的因为对于两个字符串如果 ab ba那么 a 应该在 b 前面。string largestNumber(vectorint nums) { vectorstring strs; for (int num : nums) strs.push_back(to_string(num)); sort(strs.begin(), strs.end(), [](string a, string b) { return a b b a; }); if (strs[0] 0) return 0; string ans; for (string s : strs) ans s; return ans; }这题的贪心点在于只要每次比较两两拼接谁更大得到的全局排序就是最优的。它完美体现了贪心里的“两两比较局部最优整体也最优”的思维方式而且代码很简洁适合拿来给别人展示你对贪心的理解。我做这道题时还踩过一个细节坑如果所有数字都是 0拼接结果应该返回 0 而不是 000...0。代码里就通过判断strs[0] 0来提前返回。这种边界虽然很小但面试时很容易因此被扣分。最后说两句做了这么多道贪心题之后我真实的感受是贪心算法不像动态规划那样需要你建立状态和转移方程它的难点全在于“敢不敢用、能不能证明”。面试时候最不讨喜的回答方式是直接说“我觉得这题可以用贪心”然后开始写代码。更好的回答是先把贪心策略讲出来再举一个小用例验证再说“这个策略可以用交换论证证明是最优的”。哪怕你证明得不那么严密面试官也会觉得你有算法思维这是实战里特别管用的小技巧。另外再分享一个我自己的复习方法每做完一道贪心题我都会在本子上记下两句话——第一句是“这题的最优局部选择是什么”第二句是“为什么局部最优能推出全局最优”。两句话想不清楚说明还没完全吃透过两天我会重新回来做一遍。用这个方法我复习一周之后贪心题的基本上能做到 10 分钟内锁定思路。希望这套方法对你也有用。