刷题刷到贪心不少人的第一反应是“这玩意不是很简单吗就是每步选最优”结果一到力扣上AC率被打回原形。原因很简单贪心算法的代码量确实小但难的不是写而是“判断”。判断一道题能不能贪、怎么贪、为什么这么贪对这三关过不了代码写得再顺手也没用。我刷题三年多从力扣周赛到算法工程师面试贪心是唯一一个让我反复“顿悟”的算法。说白了贪心是那种“看答案觉得理所当然自己做死活想不到”的类型。这篇是贪心系列的第一篇我想用尽量直白的语言把贪心的底层逻辑、判断方法、经典套路和实操代码一次性讲透。适合刚开始刷题的新手也适合那些刷了题但总觉得“题题不一样、总结不出规律”的朋友。1. 贪心算法到底在贪什么直觉、定义与底层逻辑1.1 一个买咖啡的例子贪心的日常直觉先别管定义说一个我经常用来给同事解释贪心的例子。假设你手上有若干张代金券每张面额不同你想买一杯25块的咖啡目标是让付出去的券“张数最少”。这时候大多数人的直觉是什么先从面额最大的券开始凑不够再用小面额的补这就是贪心。这个场景里“每步都用当前最大的券”就是局部最优选择而最终得到“总张数最少”就是全局最优。贪心算法的核心就是这个思想每一步都取当前状态下的最优解希望通过一系列局部最优拼出全局最优。再比如开会抢会议室。一个会议室能被多个会议分时占用给你一堆会议的开始和结束时间问你最多能安排多少个会议。标准做法是按结束时间从早到晚排序先安排最早结束的那个然后跳过所有和它冲突的会议再从剩下的里面重复这个过程。这也是贪心。这些例子听起来都顺理成章好像没什么难度。但难就难在“顺理成章”这三个字——并不是所有问题都适合这么干。找零钱问题就是个经典反例。假设面额是1、5、11要找15元贪心会先拿11再拿4个1一共5张但最优解明明是可以拿3个5一共3张。同样是贪心在咖啡场景里对在找零场景里就错。这说明贪心不是万能模板而是有条件的。1.2 让贪心成立的两个关键条件我在面试别人或者被人面试的时候发现大部分人对贪心的理解都只停留在“局部最优推全局最优”这句话上能说清楚背后条件的没几个。其实贪心能成立必须要满足以下两点缺一不可。第一最优子结构。问题的最优解包含子问题的最优解。换句话说你每一步做出来的选择必须能把问题拆成一个“规模更小的同类问题”而且小问题的最优解不会被大问题的选择影响。用刚才的会议室例子你选了最早结束的会议A之后剩下的问题就变成了“从A结束时间开始在剩余会议中选最多不重叠的会议”这是一个新的独立子问题。第二贪心选择性质。这是和动态规划最本质的区别。动态规划会保留所有可能的子问题结果最后比较取最优而贪心直接锁定当前步的最优选择不再回头考虑其他选项。这就要求你必须有证据证明“当前这一步选了它后面一定不会吃亏”。所以你看贪心的代码往往只有几行但写代码之前做的逻辑论证才是真正值钱的部分。这也是为什么面试官特别爱考贪心——它能快速暴露一个人是“背模板”还是“真理解”。1.3 贪心与暴力枚举、动态规划的关系很多初学者会把贪心和动态规划搞混。我打一个比方暴力枚举像是把所有路都走一遍最后挑最好的那条动态规划像是一个人在每个岔路口把每条路都记录下来边走边更新而贪心则像是一个只认死理的人在每个路口只看一眼哪条路在最前面有棵大果树然后扭头就走赌它后面还是最好的。暴力枚举时间复杂度高但永远不会错。动态规划能保证最优但需要额外的空间记录状态。贪心的时间和空间代价都最低但它赌的是“局部最优就是全局最优”。这就引出贪心在刷题里的一个很实用的心态别急着否定暴力枚举。很多时候我拿到一个新题第一反应是先想暴力怎么做然后在这个基础上去优化最后看能不能用贪心替换掉某些“不必要的比较”。不要觉得暴力枚举很丢人它是验证贪心正确性的最有力工具。2. 怎么判断一道题能不能贪常见套路与反例思维2.1 四种“贪心友好”的典型题型刷题多了你会发现测试机构里的贪心题其实翻来覆去就那么几个类型。我根据自己的刷题经验整理了四类最常见的你可以当做一个“贪心触发清单”。第一类是分配问题。典型代表就是LeetCode 455分发饼干。题目给你一些孩子的胃口值和一些饼干的尺寸问你最多能满足几个孩子。这类题目的特征是有两组资源一组是需求一组是供给让你求最大匹配度。贪心思路通常是先把两组数据都排序然后用双指针一个对一个。第二类是区间问题。典型代表是LeetCode 435无重叠区间、LeetCode 56合并区间。特征是有若干个区间让你求不重叠区间的最多数量、要删除几个区间才不重叠、或者合并有交集的区间。这类题的核心“贪心选择”基本都藏在排序规则里。第三类是跳跃/范围覆盖问题。典型代表是LeetCode 45跳跃游戏II和LeetCode 55跳跃游戏。特征是你站在一个起点每次可以从当前位置跳到某个范围内的任意位置求能否到达终点或者最小步数。贪心体现在维护“当前能走到的最远位置”上。第四类是顺序决策问题。典型代表是LeetCode 134加油站。特征是你按顺序经过若干站点每个站点有收入和消耗问从哪个点出发能走完全程。这类题目表面上像模拟但实际上可以优化成一次线性扫描的贪心。2.2 怎么快速否定一个错误的贪心策略这是我在刷题过程中收获最大的一课。以前我拿到一道题凭感觉想出一个贪心策略然后直接开写写完一提交WA然后就开始怀疑人生。后来我学乖了动手写代码之前先花三分钟找反例。找反例的方法是盯着你的贪心策略想办法构造一个最刁钻的输入让它做出一个错误的决定。比如你心想“每次选结束时间最晚的区间”那就构造两个区间一个特别长、一个特别短短的完全被长的包含——如果你选了长的那个剩下就没得选了而选短的还能再选一个这就找到了反例。找反例不是瞎构造我总结出三个切入点。第一从“大小/多少”的角度构造极端值比如一个特别大一个特别小。第二从“顺序”的角度乱序你的策略假设某种顺序最优那就构造一个完全相反的输入顺序。第三从“包含关系”的角度出发构造一个完全包含另一个区间、物品、方案的情况。如果你能在3分钟内找到反例那这个贪心策略基本废了别犹豫换思路。如果找不到反例也别急着开写再想想“为什么找不到”这个过程会逼你把逻辑理清楚。2.3 排序是贪心的重头戏区间类问题的通用套路区间类问题有一个万能的思考框架这个框架我刷了不下二十道区间题之后才彻底总结出来可以说覆盖了LeetCode上一个庞大的题目家族。第一步想清楚按什么排序。区间题一般有两种排序选择按左端点排或按右端点排。我之前说过会议室问题按右端点排序能让你选择的每个区间结束得尽可能早给后面留下更多空间。而合并区间这种题反而常按左端点排序因为你关心的是覆盖范围能不能接上。第二步用一个变量维护“当前已选区间的最右端点”。然后从头到尾扫描排序后的区间逐个判断当前区间是否和上一个已选区间冲突。第三步根据题目要求决定冲突时怎么办。如果是“求最大不重叠区间数”冲突时就跳过当前区间如果是“求删掉最少数区间使不重叠”那冲突时保留右端点更靠左的那个。这套流程我建议你当成口诀背下来。后面我会用无重叠区间这道典型题给你完整走一遍这个流程。3. 四道经典题型的逐层拆解从思路到代码3.1 分发饼干最简单的贪心入门题LeetCode 455分发饼干是无数人第一次接触贪心时刷的题。题目不难但它特别适合用来体会“贪心策略是怎么想出来的”。先看暴力想法把所有分配方案全部列出来看哪种方案能满足最多孩子。这当然可行但组合数爆炸。再想贪心如果一个孩子胃口小一个孩子胃口大现在手头只有一块小饼干和一块大饼干该把大饼干给谁直觉一定是给小胃口的孩子因为大胃口的孩子可能吃不下小饼干但小胃口的孩子吃大饼干肯定没问题。换句话说用尽量小的饼干满足尽量小的胃口把大饼干留给后面可能更需要的孩子。实现上直接排序加双指针。g数组是胃口s数组是饼干尺寸。两个索引分别从0开始如果当前饼干能喂饱当前孩子两个指针都往后走如果当前饼干喂不饱当前孩子只移动饼干指针换成更大的饼干再试。这个逻辑跑完答案是稳定正确的。为什么贪心在这里成立因为孩子和饼干之间的匹配是单调的——饼干越大能喂饱的孩子范围越大。所以“小饼干先满足小胃口”是一个不会变差的选择具备贪心选择性质。3.2 跳跃游戏系列贪心与“最远可达”的博弈LeetCode 55跳跃游戏和LeetCode 45跳跃游戏II是两道特别能考验贪心功底的题推荐放一起刷。先看简单版。判断从起点出发能不能跳到最后一个下标。最短的贪心写法是用一个变量right记录“当前能到达的最远下标”然后遍历数组不断更新这个值。需要注意遍历范围是0到right因为超出这个范围你根本走不到循环过程中如果right已经能覆盖最后一个位置直接返回True。再看升级版跳跃游戏II要求你用最少步数跳到终点。这道题比简单版难了一个维度但核心还是维护“最远可达”。我的实现思路是记录当前这一步能到达的最大位置curEnd同时记录从curEnd之前的位置起跳能得到的全局最远位置farthest。每走一步当i到达curEnd时意味着这一步能走的范围已经全部探索完了此时步数加一curEnd更新成farthest。这个过程本质上是在做BFS把每一跳能到达的区域划成一“层”一层一层往外扩张扩到终点时层数就是答案。有些人可能会问为什么farthest是最优的我换个角度解释。你在第1跳能到达的范围是[0, nums[0]]在这些位置中你应该选择跳到一个能让“下一跳的覆盖范围”最大的位置。因为下一跳覆盖范围越大越有可能更早覆盖到终点。这就像你走路时要跨一个泥坑你会找一块踩上去能让下一步跨得最远的石头而不会选一块近但低的石头。这就是贪心选择性质的体现。3.3 无重叠区间吃透一道题拿下一类区间题区间调度可以说是贪心算法在面试里出镜率最高的题型。每一本算法书、每一份刷题笔记都会提到它网上像labuladong的刷题笔记也把这类题归得明明白白。LeetCode 435无重叠区间题面说给一个区间集合求需要移除区间的最小数量使剩余区间互不重叠。做题之前先想清楚“最少移除多少个区间”等于“区间总数”减去“最多能保留多少个互不重叠的区间”这是第一步转化。第二步是关键怎么选彼此不重叠的区间能让数量最多正确策略是按右端点升序排序选择能选的所有区间每个区间右端点越小留给后续区间的空间就越大。这个策略我在前面已经铺垫过好几次了。扫描时维护一个变量lastRight表示当前已选区间中最后一个区间的右端点。每遍历到一个新区间如果它的左端点大于等于lastRight说明不冲突选它然后更新lastRight否则说明冲突跳过。为什么按右端点排序而不是左端点我给你举一个反例。如果有三个区间[1,10]、[2,3]、[4,5]按左端点排序会先选[1,10]一个区间都容不下别了按右端点排序会先选[2,3]再选[4,5]能保留两个。看见了吧排序规则选错结果天壤之别。3.4 加油站环形路线上的贪心妙手LeetCode 134加油站是一道看起来很绕、想明白后特别爽的题。一圈路上有若干个加油站每个站可以加油但从这个站开到下一个站要消耗油。已知每个站的油量和到下一站的耗油量问你从哪个站出发能跑完一整圈。暴力的做法是枚举每个站点作为起点模拟跑一圈看油够不够O(n^2)的复杂度。但贪心可以做到O(n)。核心观察是两条。第一如果总油量小于总耗油量那无论如何都跑不完一圈。第二如果从某个起点A出发车开到站点B的时候油量变成负数那说明A和B之间的任何一个站点都不适合做起点。为什么因为从A出发到B的过程中车上油量一直是非负的这说明A是最佳出发点之一如果从A中途的C出发经过C到B这段路时C之前的油量优势全部丢失了只会更早没油。所以算法只需要做一次线性扫描。用一个total变量累计gas[i]-cost[i]如果total最后为负直接返回-1。同时用一个tank变量累计当前路段的油量一旦tank为负就把起点暂定为i1tank清零重新累计。最终返回暂定的起点。这道题告诉我一个道理贪心的“贪”不一定总是“选最大、要最多”有时候它表现为“发现问题及时止损、果断更换起点”。理解到这一层你的贪心才算入了点门。4. 实操记录三题带你走完贪心刷题全流程4.1 分发饼干双指针闭着眼睛写这道题我建议新手第一个自己动手写因为它短而且能让你体会“排序是贪心的一半”。def findContentChildren(g, s): g.sort() s.sort() i 0 j 0 while i len(g) and j len(s): if s[j] g[i]: i 1 j 1 return i看这段代码重点在j的位置。无论饼干能不能满足当前孩子j都会往后走因为这块饼干如果在更小的孩子那儿都不行那对后面胃口更大的孩子更不可能行它直接废弃。只有满足时才i 1表示这个孩子被喂饱了。这个细节是双指针的精华。时间复杂度的关键在于排序O(n log n)两个指针各扫一遍空间复杂度O(1)。面试时问复杂度一定不要只说“是O(n)”而忽略排序这种细节理解不到位会露馅。4.2 跳跃游戏IIBFS视野下的最少步数这道题写起来不复杂但边界条件很容易错。先看代码再解释。def jump(nums): n len(nums) if n 1: return 0 cur_end 0 farthest 0 jumps 0 for i in range(n): farthest max(farthest, i nums[i]) if i cur_end: jumps 1 cur_end farthest if cur_end n - 1: break return jumps我当时的第一个错误是没加if n 1这个边界判断结果是数组只有一个元素时莫名返回了1。第二个容易出错的地方是i cur_end的更新时机初学者常常忘了更新cur_end后要检查是否到达终点导致多做一次循环。还有一个细节循环的范围是range(n)而不是range(n-1)因为我是在i到达cur_end时才步数加一当i来到最后一个位置时如果还没break说明最后一步还没计入结果这时让循环走到最后一个位置并更新是安全的。不过更稳妥的写法是循环只走到n-2这样逻辑更清晰。你可以自行验证两种写法都能过我实际测试中更推荐第二种因为不容易出现“步数多算”的边界问题。4.3 无重叠区间把“删几个”翻译成“最多留几个”这道题的价值在于它让你真正理解贪心中的转化。先来看我常用的解法。def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) last_right intervals[0][1] keep 1 for interval in intervals[1:]: if interval[0] last_right: keep 1 last_right interval[1] return len(intervals) - keep核心代码只有十来行但每一步都值得细说。先把区间按右端点从小到大排这是那个“给后面留空间”的贪心策略。然后初始化保留的第一个区间是右端点最小的那个计数器keep置为1。接着从第二个区间开始遍历如果左端点不比当前保留区间的右端点小说明两者不重叠保留它并更新last_right。如果重叠就跳过期望右侧更晚结束的区间更“省空间”。真正容易出错的是interval[0] last_right这个比较。题目说“边界接触不属于重叠”比如[1,2]和[2,3]是可以共存的所以判断时要用而不是。这个点我当时做的时候就因为用错符号WA过一次印象特别深。4.4 我的高效刷题顺序与时间分配建议在最终给出刷题路线之前先说说我走过的弯路。我一开始刷贪心是“随缘式”的今天一道给饼干明天一道跳跃没有明确的难度递进结果就是每一道题对我都是全新的形不成知识网络。后来我调整了一个顺序效率明显提升现在分享给你。第一优先级是基础分配题比如分发饼干、LeetCode 1710卡车上的最大单元数。这两题练的是“排序双指针”每天掌握一题第二天至少能默写出来。第二优先级是区间类从无重叠区间开始然后做LeetCode 452用最少数量的箭引爆气球、LeetCode 56合并区间。这三道题做好区间题你基本能触类旁通。第三优先级是范围类也就是跳跃游戏I和II这两题需要一点抽象思维建议放在有手感之后再做。最后做加油站这类“反直觉”的顺序决策题。每道题做完后我会强迫自己在注释里写一行“贪心策略一句话总结”。比如无重叠区间写的是“按右端点排序能留就留”跳跃游戏II写的是“每次跳到最远能覆盖的位置”。这个习惯坚持下来复习时我几乎不用重新看题目只需要扫一眼自己的注释就能回忆起来。5. 常见问题与排查技巧实录5.1 三个典型的翻车现场刷贪心题最常见的翻车有三类每类我都亲历过给你提前排个雷。第一类是策略方向搞反。比如分发饼干有人觉得应该让大饼干先满足大胃口的孩子结果小饼干全浪费了。看起来好像逻辑没毛病大胃口的满足了小胃口的总能找到合适的实际上却可能出现大饼干给了一个胃口中等的孩子导致更大胃口的孩子没得吃而小饼干也浪费了。反例一构造就清楚。第二类是排序规则选错。区间题里按左端点排还是按右端点排直接决定成败。这个问题我从道理上理解过不下一百次但真到做题时还是会犯。我现在的方法是直接背场景最优化不重叠区间数量按右端点排求覆盖区间长度按左端点排区间合并也是按左端点排。第三类是忽略边界条件。跳跃游戏II的空数组、单元素数组无重叠区间的空数组加油站的单站点环。这些边界我吃过太多亏了所以现在无论时间复杂度多优秀开写前都会先把这个题目的特判列出来养成肌肉记忆。5.2 贪心证明到底怎么做交换论证法入门这一小节可能是这篇文章里最“学院派”的部分但我觉得它恰恰是最值钱的。面试的时候如果你只写代码说不上为什么很容易被扣印象分反过来能清晰讲出贪心正确性绝对是个加分项。最常用的证明方法是交换论证法。核心逻辑是假设全局最优解里的某一步选择和你贪心算法的选择不同然后证明把最优解里的那个选择换成贪心选择不会让结果变差。既然任何最优解都能一步步换成贪心解而质量不降那贪心解也就是最优解。我举一个最直观的区间调度例子。最优解选的第一个区间是A贪心选的是右端点最小的区间B。因为B的右端点小于等于A的右端点所以A能容纳的后续区间B也一定都能容纳。把A替换成B剩下的可选区间只会更多不会更少。于是每换一步都不吃亏经历若干次替换后最优解就变成了贪心解质量完全一致。这个论证过程听起来不难但你得形成书面语言面试时能不卡壳地讲出来。5.3 调试技巧跟暴力枚举“对拍”是终极排查法终端里写贪心算法最容易出现的情况是测试用例都过了一提交AC不了。这个时候我强烈推荐一个方法——写一个暴力解法然后用随机数据对拍。具体操作很简单。先用最粗暴的枚举方式写一个绝对正确的函数哪怕复杂度是O(n!)、O(2^n)再写你的贪心函数。然后写一个循环每次生成随机的小规模数据比如n的取值在1到8之间同时跑暴力结果和贪心结果只要发现不一致就立刻能定位到反例。我之前做一道区间贪心题测试了几组手写用例都过了一提交就WA。用对拍方法跑了不到两分钟生成了一组包含六个区间的数据贪心结果返回3暴力返回4。顺着那组数据一分析发现我的排序规则确实有问题。从那以后凡是用贪心解题如果我怀疑策略有问题都会写个对拍小脚本验一验。这个方法不仅适合做LeetCode也适合在OJ平台刷题时使用。很多同学在OJ上WA了二十次都找不出原因其实就是因为人工构造的测试数据太普通没有命中贪心策略的脆弱点。5.4 面试现场怎么把贪心题讲到面试官点头如果你准备算法面试贪心题是必须掌握的面试题型。根据我的面试经验面试官问贪心题很少是只为了看你写代码他们更想看你“如何得出贪心策略”。我推荐的回答框架分为四步你可以在面试前模拟练习。第一步复述题意把输入输出讲清楚。第二步快速说一个最朴素的暴力解法然后点出它的瓶颈。第三步抛出贪心策略最好能顺带说出“我这么选是因为它具备贪心选择性质”再举一个小反例证明其他策略不行。第四步写代码边写边解释每一步在做什么。千万不要一上来就闷头写代码。哪怕你的贪心策略是对的如果面试官没理解你的思路他也无法确认你是不是背题背出来的。我在一次模拟面试中就遇到过候选人直接写代码写完说“这就是贪心”问他为什么贪心是对的支支吾吾半天。最后代码满分但评价还是降了一档。这个系列的下一篇我会沿着贪心往下展开接着讲“区间合并类问题”和“带权值的最优策略选择”这两类题目在笔试里出现的频率更高也更考验综合能力。这篇先写到这如果你能从里面至少带走一个判断反例的习惯那就算没白读。