刷题刷到第27天终于轮到了贪心算法。说实话之前我对贪心一直有点“偏见”总觉得它不像动态规划、回溯那样有清晰的框架每道题像是灵光一现很难系统化。但真正刷完一批经典题目之后我发现贪心其实也有迹可循它考验的不是模板记忆而是对“局部最优能不能推出全局最优”的判断力。今天这篇就把我这段时间啃贪心的完整路径整理出来核心思路、经典题型、实战技巧、常见坑一次讲透。贪心算法Greedy Algorithm解决什么问题一句话概括每一步决策都取当前看起来最好的选择希望最终累积出全局最优。它的典型应用场景包括资源分配、区间调度、跳跃类问题、求最大最小值问题。这篇文章适合三类人准备笔试面试的求职者、算法刚入门想建立题型体系的新手、以及在贪心和动态规划之间经常选错方向的同学。只要你正卡在“这题我该不该用贪心”的纠结里这篇就是为你写的。1. 贪心算法到底在贪什么核心思路与适用范围1.1 局部最优到全局最优贪心的底层逻辑贪心的决策过程有一个鲜明特征只看现在不看未来。走到某一步时当前状态有哪些可选方案直接选那个在当下看起来最优的然后往下走绝不回头。这和现实里的“走一步看一步”很像比如你逛超市想买最划算的组合但又不允许反复比较所有搭配时就只能在每个货架前选最顺眼的商品。但这里有一个容易误解的地方贪心并不保证一定得到全局最优。它只在某些特定结构的问题里成立。比如找零钱问题如果用1、5、10、20这些面额每次优先找最大面额最后一定是最少张数可如果货币面额改成1、5、11同样是找15块贪心会先拿11再拿4个1一共5张而最优解是3张5块。这就是经典的贪心失败反例。所以在学习贪心时我的建议是先别急着背题型而是要把这句话刻在脑子里贪心不是“一种算法模板”而是一种“问题性质”。只有当问题的结构保证每一步的局部最优能拼出全局最优时贪心才是正确解法。后续所有题目的分析本质上都是在回答“这个性质到底存不存在”。1.2 什么时候才敢用贪心两个必要条件判断一道题能不能用贪心理论上需要满足两个条件贪心选择性质和最优子结构。贪心选择性质指的是通过一系列局部最优选择能最终拼出全局最优解。说得直白一点就是你在每一步做的“最划算选择”永远不阻碍后面拿到更好的结果。最优子结构则是指整个问题的最优解包含了子问题的最优解。这两个条件听起来抽象但实际操作中我们可以用一种更接地气的方式去判断先别管证明直接手推三到五个测试用例如果每一步贪心策略在这些用例里都正确而且你举不出反例那就可以大胆写。写完之后再回头想想证明如果实在想不出来再去找题解看别人的证明逻辑。这里我额外补充一张对比表格帮你彻底区分贪心和动态规划因为太多人在这两者之间摇摆不定。对比维度贪心算法动态规划决策依据当前状态下的局部最优所有子问题状态的综合比较是否回溯不回溯一条路走到底通过状态转移比较多个分支状态依赖只依赖当前状态依赖多个历史子问题适用条件贪心选择性质 最优子结构最优子结构 重叠子问题代码风格通常十几行简洁需要DP数组状态较多典型代表区间调度、跳跃游戏、最小生成树背包问题、编辑距离、最长子序列这张表是我每次刷题前都会在脑子里过一遍的。遇到一个题目先想它是“一条路走下去”还是“有多条路要比较”往往答案就清晰了一半。1.3 贪心的天敌哪些场景不能碰贪心最大的天敌就是“需要全局统筹”的问题最典型的就是0-1背包。每个物品有重量和价值背包容量有限目标是装下总价值最大的一组物品。如果按“单位价值最高”来贪心很容易出错一个钻石单位价值超高但太重塞进去之后剩余容量装不了两个便宜但总价值更高的物品。这种情况下局部最优是钻石全局最优可能是一堆小物件贪心直接翻车。再比如股票买卖问题如果允许无限次交易但每次有手续费简单的“见涨就卖”贪心可能被手续费吃掉利润我需要维护两个状态持有和不持有才能算出最优。这种时候就该上动态规划而不是硬贪。判断能不能用贪心的一个实用技巧就是看“当前选择会不会影响未来的可选项”。如果在选择A之后未来的决策空间被严重压缩而且没有一个数学性质能保证这种压缩无损那大概率不能贪心。反过来如果选择A之后下一步的决策完全不关心A具体选了哪个只关心当前状态值那贪心就很有希望。这就是常说的“无后效性”也是贪心和动态规划最本质的分水岭。2. 入门必刷的三种贪心题型分配、序列与跳跃2.1 分配类分发饼干和分发糖果先看最经典的455. 分发饼干。题目给两个数组一个是孩子的胃口值g一个是饼干尺寸s每个饼干只能喂一个孩子问最多能满足几个孩子。这道题看答案觉得很简单排序加双指针就完了但自己第一次写很容易绕晕。我当时卡在一点“到底用饼干去匹配孩子还是用孩子去匹配饼干”这里有一个比较稳的解法是先给两个数组都排序然后用小饼干优先满足小胃口的孩子一个指针i指向孩子另一个指针j指向饼干。遍历每一块饼干如果当前饼干能满足g[i]i就往后移动一位最终返回i。class Solution { public: int findContentChildren(vectorint g, vectorint s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i 0; for (int j 0; j s.size() i g.size(); j) { if (s[j] g[i]) i; } return i; } };为什么小饼干优先喂小胃口因为大饼干是稀缺资源它既能喂小胃口也能喂大胃口。如果用大饼干喂了小胃口后面遇到大胃口时可能就没有合适的饼干导致总的满足数量下降。反过来小饼干喂不了大胃口却可以喂小胃口把小胃口解决掉大饼干留给大胃口整体满足数才不会浪费。这就是典型的“让资源匹配恰到好处”。再看一道容易怀疑人生的分配题135. 分发糖果。每个孩子至少分到1个糖果且评分高的孩子要比左右邻居拿得多求最少需要多少糖果。我第一次做这道题时试图一次遍历同时处理左右两边的情况结果边界判断写得又长又乱还怎么调都不对。后来才明白这种“左右都有限制”的问题正确姿势是拆成两个方向分别处理先从左往右遍历只保证右边孩子比左边孩子多如果评分更高这个方向可以给所有“右边高”的孩子发够糖果再从右往左遍历只保证左边孩子比右边孩子多同时要取两边计算结果的较大值。int candy(vectorint ratings) { vectorint candies(ratings.size(), 1); for (int i 1; i ratings.size(); i) { if (ratings[i] ratings[i - 1]) candies[i] candies[i - 1] 1; } for (int i ratings.size() - 2; i 0; --i) { if (ratings[i] ratings[i 1]) candies[i] max(candies[i], candies[i 1] 1); } return accumulate(candies.begin(), candies.end(), 0); }这道题的核心启发是当一个约束同时涉及前后两个方向时贪心策略未必能一次完成可以把约束拆成两个单方向的贪心各做一次最后取交集。这个技巧在不少题目里都能复用尤其适合处理“既要大于左边又要大于右边”这类对称条件。2.2 序列类摆动序列和最大子数组和376. 摆动序列要求找出数组中最长的摆动子序列长度。所谓摆动就是相邻元素的差值一正一负交替出现比如[1,7,4,9]中差值分别是6、-3、5正负交替。这道题最关键的观察是我们不需要真的去删除元素构造子序列只要统计数组中的“拐点”数量就行。想象你在一张折线图上看走势连续上涨之后出现下跌的那一瞬间就是一个转折只有趋势发生翻转的位置才计入长度。代码里用prediff记录上一次的差值方向curdiff记录当前差值当两者一正一负时说明出现了摆动计数加一然后更新prediff。int wiggleMaxLength(vectorint nums) { if (nums.size() 2) return nums.size(); int prediff 0, curdiff 0, count 1; for (int i 1; i nums.size(); i) { curdiff nums[i] - nums[i - 1]; if ((curdiff 0 prediff 0) || (curdiff 0 prediff 0)) { count; prediff curdiff; } } return count; }这里有两个细节特别容易错。第一prediff初始值设为0是为了让第一个上升或下降趋势也能被判断为一次摆动。第二个细节是平坡的情况连续相等时curdiff为0此时不能更新prediff否则会把平坡后面的真实趋势漏掉。我当初就在这里翻过车如果不加“prediff 0”和“prediff 0”这些边界连续平坡后再转折就会被忽略掉结果偏小。53. 最大子数组和是另一个经典中的经典。给定一个整数数组找出和最大的连续子数组返回最大和。贪心思路非常清爽用一个count变量累加当前位置元素只要累加结果还大于0就说明它对后续子数组是有“正向贡献”的可以继续累加一旦count变成负数说明前面的这一段对后面只会拖后腿直接丢弃重置为0。遍历过程中不断用count更新答案。int maxSubArray(vectorint nums) { int result nums[0]; int count 0; for (int num : nums) { count num; if (count result) result count; if (count 0) count 0; } return result; }这个题有个非常经典的坑result的初始值不能是0否则输入全是负数时就会返回0而不是最大那个负数。我第一次写的时候就把result初值设成0结果在一个[[-1,-2,-3]]样式的用例上直接错掉。另外这道题在网上也被归类为动态规划因为它的滚动变量写法其实就是一维DP的压缩版本但从贪心角度看也完全说得通两种视角都能解释很有意思值得反复品味。2.3 跳跃类从跳跃游戏I到跳跃游戏II55. 跳跃游戏是贪心题里的风向标。每个位置最多能跳几步问能不能从下标0跳到最后一个位置。这道题不建议直接模拟跳跃过程因为每一步有很多跳法模拟起来容易漏。更稳的做法是维护一个最远覆盖范围cover初始是0然后遍历下标只要当前下标i在cover范围内就尝试用i nums[i]更新cover让它越远越好。如果cover已经大于等于数组最后一个下标直接返回true。bool canJump(vectorint nums) { int cover 0; for (int i 0; i cover i nums.size(); i) { cover max(cover, i nums[i]); if (cover nums.size() - 1) return true; } return false; }关键点是遍历范围不是0到n-1而是0到cover。如果cover还够不着当前下标i说明前面的跳跃上限已经到底了根本走不到i后面也不用再看了。这个“覆盖范围”的思想是后续很多贪心题的地基比如合并区间、视频拼接等本质都是在维护一个最远能触及的边界。45. 跳跃游戏II难度升级假设一定能到达终点求最少跳几次。我第一次拿到这题时思考的方向是用回溯但一看到数组长度是10的4次方量级就放弃了。贪心做法很巧妙维护两个变量curEnd表示当前这一步能跳到的最远位置nextEnd表示再跳一步能到达的最远位置。遍历数组的过程中不断用i nums[i]更新nextEnd当i走到curEnd时说明这一步覆盖的区域已经全部检查完还没到终点那就必须跳一步步数加一然后把curEnd更新为nextEnd。int jump(vectorint nums) { int curEnd 0, nextEnd 0, step 0; for (int i 0; i nums.size() - 1; i) { nextEnd max(nextEnd, i nums[i]); if (i curEnd) { step; curEnd nextEnd; } } return step; }为什么这个贪心是最优的因为在当前步覆盖的区间内我选择“跳到能让下一步覆盖范围最大的那个点”这并不会增加步数却让未来的可选择范围最大化。相当于每一步都用同样的代价换取最大的未来收益自然就是最少步数。我当时反复模拟了好几遍才真正理解这个“当下边界 下一步边界”的双层结构建议你也多走几遍用例感受会更深刻。3. 进阶战术区间调度与数学类贪心3.1 区间问题的统一套路排序是关键区间类问题是贪心算法里最成体系的一块几乎可以归类成一个固定套路排序 贪心选择。难点在于搞清楚“按左端点排还是按右端点排”。我自己的经验是如果题目要求“为后续区间腾出更多空间”比如无重叠区间、最少箭射气球那通常按右端点排序如果题目要求“把有交集的区间合并起来”比如合并区间那就按左端点排序。这个选择的本质原因是右端点越小给后面留下的空档越大贪心策略才有发挥空间而左端点排序则方便你从头开始顺次合并。举一个典型例子452. 用最少数量的箭引爆气球。每个气球在x轴上是左右端点构成的一个区间一支箭可以射穿所有与之相交的气球问最少几支箭。按右端点排序先拿第一个区间的右端点作为射箭位置。遍历后面每个区间只要它的左端点小于等于这个射箭位置说明这支箭能射中它不需要新箭一旦出现左端点大于射箭位置才需要射第二支箭并更新射箭位置为这个新区间的右端点。int findMinArrowShots(vectorvectorint points) { sort(points.begin(), points.end(), [](vectorint a, vectorint b) { return a[1] b[1]; }); int arrow 1; int pos points[0][1]; for (int i 1; i points.size(); i) { if (points[i][0] pos) { arrow; pos points[i][1]; } } return arrow; }这里有个特别容易踩的边界题目说“两个区间相切时也算能被同一支箭射中”所以判断条件要用而不是。我因为惯性思维用了结果在相切用例上输出多了1排查了半天才意识到是边界符号的问题。区间类题目的边界条件经常决定了整个答案的正确性写之前一定要仔细读题看区间是开区间、闭区间还是相切算相交。类似的还有435. 无重叠区间按右端点排序后能保留的区间就是那些“结束早”的区间删掉多少个等于总数减去能留下的个数。56. 合并区间则按左端点排序维护当前合并区间的右边界遇到有交集的就更新右边界遇到没交集的就收尾并开启新区间。763. 划分字母区间稍微特殊一点需要先记录每个字母最后一次出现的位置再遍历字符串不断更新当前片段的最远边界遍历到边界就切一刀。这几道题可以放在一起集中刷刷完你会发现区间问题大同小异核心都是那个排序方向问题。3.2 数学性质的贪心取反、加油站与单调数字有些贪心题不靠区间套路而是靠数学直觉。比如1005. K次取反后的最大数组和给定一个数组可以对任意元素取反总共操作K次求最终数组的最大和。我一开始的想法是每次取反最小的数但这个策略是错的因为如果最小数是正数反复取反它反而是亏的。正确的贪心是先把数组按绝对值从大到小排序然后遍历遇到负数且还有取反次数就把它变成正数。为什么按绝对值排因为把绝对值大的负数翻成正数收益最大绝对值小的负数翻不翻对总和影响有限。处理完所有负数后如果K还有剩余就翻转绝对值最小的那个数偶数次可以忽略奇数次会减掉2倍的这个数。int largestSumAfterKNegations(vectorint nums, int k) { sort(nums.begin(), nums.end(), [](int a, int b) { return abs(a) abs(b); }); for (int i 0; i nums.size() k 0; i) { if (nums[i] 0) { nums[i] -nums[i]; --k; } } if (k % 2 1) { nums[nums.size() - 1] -nums[nums.size() - 1]; } int result 0; for (int num : nums) result num; return result; }这个题里面“先翻绝对值大的负数”和“剩余奇数次则翻绝对值最小的数”每一步都踩在数学规律上属于典型的“证明之后看起来理所当然但自己推导容易绕圈”的题目。我的建议是把它和后续的加油站、单调递增数字放到同一天刷这三道题凑在一起能极大提升你对“贪心依据”的敏感度。接着看134. 加油站。环形路线上有若干加油站每个站可加油gas[i]去下一站消耗cost[i]问从哪个站出发能走完一圈。暴力解法是逐一尝试起点O(n平方)在数据量大时直接超时。这里有个结论可以先记下如果所有站的加油总量减去总耗油量的结果小于0那无论如何都跑不完一圈直接返回-1。在有解的情况下贪心策略是从下标0开始模拟维护当前剩余油量curSum一旦curSum小于0说明从当前起点到当前站之间的任意位置出发都不可能成功干脆把起点设为i1并把curSum重置为0。int canCompleteCircuit(vectorint gas, vectorint cost) { int totalSum 0, curSum 0, start 0; for (int i 0; i gas.size(); i) { totalSum gas[i] - cost[i]; curSum gas[i] - cost[i]; if (curSum 0) { start i 1; curSum 0; } } return totalSum 0 ? -1 : start; }我第一次看到这个解法时觉得很玄学为什么curSum小于0就把起点直接跳到i1而不是往回试探后来想明白了如果从start出发到i这里油量已经为负那从start到i之间任何一个点作为起点到i时油量只会更少不会更好因为这段路上累积的净消耗是负的。所以负区间内不存在可行起点直接跳到区间后面是安全的。这一条“排除负区间”的推理就是整个题的灵魂。最后一题是738. 单调递增的数字求小于等于n的最大整数且这个数字每一位从左到右是非递减的。比如332的答案是299而1234本身就是答案。做法是先把数字转成字符串然后从右往左扫描找到第一个满足s[i-1] s[i]的位置。找到后把这个位置的前一位减1并记录一个flag表示从这个位置后面全部改成9。关键在于要一直从右往左处理因为减1之后前面可能又出现不满足单调的情况比如332先碰到32记录下标1并让前一位减变成2字符串变成322继续往左又发现32再让下标0减1变成222最后从flag1开始全部置9得到299。int monotoneIncreasingDigits(int n) { string s to_string(n); int flag s.size(); for (int i s.size() - 1; i 0; --i) { if (s[i - 1] s[i]) { flag i; s[i - 1]--; } } for (int i flag; i s.size(); i) { s[i] 9; } return stoi(s); }这个题的核心思想就一句话从高位到低位保证每一位尽量大但一旦某一位需要减1为了修复单调性后面全部拉满成9。这比从头构造要简单得多也是贪心“每一步选当前最优然后做修复”的另一个体现。4. 笔试面试实战识别贪心与证明策略4.1 一眼识别贪心题出题信号与反例验证刷题多了之后你会慢慢形成一种直觉。贪心题常见的出题信号有这么几个题目里出现“最多”“最少”“最大”“最小”“尽可能”“能否达到”这类字眼输入是一个数组或者一组区间问题要求你在一系列选择中找最优解但限制条件里没有像背包那样复杂的多维约束。拿到这样的题我先不急着写代码而是先想如果每一步都选当前最优结果会不会被影响我会动手构造几个最小的反例比如只有两三个元素的小数组分别用直觉中的贪心策略和穷举法对比。只要短时间内举不出反例而且决策确实只依赖当前状态那贪心就是第一选择。但这不代表每次都正确。我在实际刷题中总结出一个很管用的流程先用贪心秒写一版然后立刻用暴力解法或者小规模随机数据做对拍。对拍跑上几十上百组测试用例只要结果一致基本可以放心提交。这个习惯让我避开了很多“看似正确实则边界翻车”的陷阱。4.2 证明贪心正确性的三种武器笔试可以不写证明但面试时面试官经常追问“为什么贪心是对的”。这时候需要掌握三种常用的证明方法。第一种是交换论证法适用于排序类的贪心比如区间调度、活动安排。先假设最优解中存在两个相邻元素顺序和贪心规则不一致然后证明交换它们的位置后结果不会变差从而推出贪心的顺序同样能达到最优。这种方法直观又常用我写区间题时会刻意用这个思路去组织语言。第二种是反证法适用于选择类的贪心。先假设贪心选择的那个元素不在最优解里然后构造一个包含贪心选择的新解证明它比原最优解更好从而产生矛盾。比如K次取反里“优先翻转绝对值最大的负数”这个策略就可以用反证法如果不翻转它转而翻转绝对值更小的负数总和的增量一定更小不可能更优。第三种是数学归纳法适用于递归结构明显的贪心。先证明第一步贪心选择之后剩余的子问题仍然是相同结构的贪心问题而且规模小了一阶然后由归纳假设得出整体最优。实际刷题时我们不需要每次都写完整证明但至少要能在心里说明白“这个选择为什么不会让后面的结果变差”。这个思考过程本身就会反过来帮你发现隐藏的反例。4.3 高频踩坑与调试实录把这段时间踩过的坑集中整理一下希望你能绕开。第一个坑是排序方向搞反。区间调度题里合并区间按左端点排无重叠区间和射气球按右端点排搞反了大概率跑出来就是错的。这个没有捷径只能靠多练练到“看到题就知道该按哪边排”才算到位。第二个坑是边界符号用错。跳跃游戏里从左端点相切算可达要用我一开始用结果某几个用例少算了一段。类似的问题在射气球里也出现过只是方向相反要用判断是否需要新箭。第三个坑是初始值没设好。最大子数组和的result初始值必须是数组第一个元素而不是0否则全负数数组会错。这个坑几乎每个刷过这题的人都踩过属于“不能不知道”的级别。第四个坑是贪心策略正确但对特殊输入考虑不周。比如K次取反里K比负数个数多很多时剩余次数的奇偶性要单独处理单调递增的数字里找到下降点后不能只处理一次要一路往左处理到尽头。这些边界不是算法思路难而是细心问题。再分享一个我一直在用的调试习惯写贪心题的时候如果某一步不确定到底怎么选我会在代码里临时打印每一步的“贪心依据”比如当前最小值、当前覆盖范围、当前剩余油量然后对照结果看每一步的选择是否符合预期。另外强烈建议在本地搭一套对拍脚本用一个简单的暴力解法做参照随机生成小数据反复跑。这个小工具帮我省下的时间远比写它花的时间多。我个人刷下来最大的体会是贪心算法的题难的不是代码而是“敢不敢用”和“怎么证明”。很多题目用贪心只需要十几行代码但判断错方向可能在这十几行里绕半天。另外我强烈建议把贪心题和对应的动态规划题放在一起对比着刷比如最大子数组和、跳跃游戏都有DP解法两个版本对照着理解你对“什么时候贪心够用、什么时候必须DP”的感觉会建立得特别快。最后分享一个小习惯我每次刷贪心题都会先在纸上写一句“我这样选凭什么不会让结果变差”能答上来再写代码答不上来就翻题解看证明。这个习惯帮我少走了很多弯路也推荐你试试。