代码随想录算法训练营走到第35天说实话最难熬的不是题目本身而是你开始意识到贪心算法的题目背后几乎没有统一的套路。前面学二叉树的时候遍历模板摆在那里递归三部曲写熟了基本就能应付到了动态规划又有明确的状态定义和转移方程。唯独贪心每道题都是局部最优推出全局最优这一句话听起来像废话做起来全靠悟。今天这篇文章就把我在第35天刷过的几道典型贪心题拆开揉碎讲讲它们的思考方式和踩坑记录包括跳跃游戏、跳跃游戏II、加油站、分发糖果、K次取反这几道高频题。如果你也在训练营或自己刷题希望这些经验能帮你少走点弯路。1. 第35天在训练营进度中的真实坐标贪心题的收尾与总结1.1 这一天的题目其实并不多但每一道都值得反复想训练营的每日任务通常控制在3到5道题之间第35天的安排同样不会刻意堆量。到了这个阶段我的直观感受是题目数量不再是重点重点是你能不能把同一类题串起来看。贪心算法不像二分查找那样有一个明确的判定模板也不像回溯算法有标准的for循环加递归结构它是散的、碎的仿佛每道题都需要重新发明一次思路。我在第35天把前面所有做过的贪心题拉出来看了一遍分发饼干、摆动序列、最大子序和、买卖股票的最佳时机II、跳跃游戏、跳跃游戏II、K次取反后最大化的数组和、加油站、分发糖果、柠檬水找零、根据身高重建队列、用最少数量的箭引爆气球、无重叠区间、划分字母区间、合并区间、单调递增的数字、监控二叉树。这些题分布在力扣的不同区间但放在一起你会发现其实贪心策略大致能分成几个派别一类是维持一个当前最优状态然后不断推进另一类是排个序再按顺序处理还有一类是正反两个方向各扫一遍。1.2 为什么贪心比二叉树更让人心里没底二叉树阶段你至少有递归四步可以走确定参数返回值、确定终止条件、确定单层逻辑、模拟一遍。回溯阶段也有纵向上递归、横向上for循环的框架。到了贪心Carl在视频里反复强调的只有六个字局部最优、全局最优。这六个字听起来简单真正用起来却非常飘。你很难判断当前这一步的局部最优选择会不会导致后面的全局崩溃。这也是我在训练营小组里看到最多同学卡住的地方。比如跳跃游戏II大家第一反应可能是每一步都选能跳得最远的那个位置但真正实现的时候会发现问题没这么简单因为你在当前位置时并不知道后面那个最远位置是否真的值得跳过去。你要是只盯着这一步能跳多远很容易掉进局部陷阱。所以第35天的意义在我看来不是学会某一个具体的贪心算法而是建立怎么证明一个贪心策略合理的思考习惯。下面我用几道具体的题来说明这个过程。2. 跳跃游戏二连击用最远可达重新理解贪心的边界2.1 跳跃游戏I先别急着跳先算清楚能不能够到LeetCode 55题跳跃游戏给定一个非负整数数组每个元素代表你在该位置可以跳跃的最大长度判断能否到达最后一个下标。最简单、也最经典的解法是用一个变量维护当前能够到达的最远位置然后从左到右遍历数组不断更新这个最远位置。如果某个位置的下标已经大于最远可达位置说明这个地方根本到不了直接返回false。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; }我一开始做这道题的时候习惯性地想模拟跳这个过程比如用一个队列做BFS把每个位置能到达的位置都加进去。这样确实能做但复杂度一下就上去了变成O(n²)甚至更高。后来才意识到这题根本不需要模拟跳跃路径我们只关心能不能到至于怎么到、经过哪些点完全不重要。这个思维转变是贪心题的关键很多情况下你不需要知道具体方案只需要维护一个范围边界。注意一个细节这个解法的循环判断条件里i maxReach才返回false意味着当maxReach已经大于等于数组末尾下标时理论上可以提前退出循环但即使不退出也能正常遍历完。边界上要小心空数组和长度为1的数组不过题目至少给了一个元素长度为1时直接返回true就行。2.2 跳跃游戏II最少步数是怎么通过更新边界算出来的跳跃游戏II是跳跃游戏I的升级版要求用最少的跳跃次数到达数组最后一个位置。这道题比I难了一个数量级。我最初的想法是贪心每一步都跳最远但细想之后就发现了问题跳得最远不代表总数最少。举个反例[2, 3, 1, 1, 4]第一步从位置0出发最远能跳到位置2但最优解是跳到位置1因为位置1能跳到4。所以每步跳最远这种看似贪心的策略在这里根本就是错的。正确的贪心方式是维护两个变量当前这一步能覆盖到的右边界curEnd以及从这个边界内所有位置出发所能达到的全局最远位置farthest。遍历数组时持续更新farthest一旦i走到了curEnd说明你已经把当前这一步所有可能的位置都看完了必须跳一步然后把curEnd更新为farthest。int jump(vectorint nums) { int jumps 0; int curEnd 0; int farthest 0; for (int i 0; i nums.size() - 1; i) { farthest max(farthest, i nums[i]); if (i curEnd) { jumps; curEnd farthest; } } return jumps; }这段代码的核心思想是在当前步的可达区间内找出下一步能去的最远位置等走到当前区间末尾时再统一跳一步。换句话说跳跃不是站在每个点上做选择而是先把整个区间的潜力计算完再做一次决定。这个延迟决策的思路在贪心题里非常常见也是跳跃游戏II最有价值的地方。2.3 我在提交里踩过的样例坑跳跃游戏II有几个边界细节我在训练营提交的时候反复绕进去过循环条件是i nums.size() - 1而不是i nums.size()。因为最后一个位置不需要再跳了多跳一次会错。题目保证了一定能到达最后一个位置所以jumps不会越界。但如果你自己写题做变体最好加一个curEnd nums.size() - 1的提前退出判断可以省掉无意义的遍历。curEnd初始化为0farthest初始化为0当i 0时就会触发第一次跳跃。这其实是符合直觉的因为你站在起点就要先跳第一步。这些细节看起来小但面试时写错一个就很可能被判定为思路不够严谨。我自己就在第一次写跳跃游戏II时忘了减1提交一次WA之后才反应过来。3. 加油站与分发糖果两道反直觉的贪心经典题3.1 加油站为什么敢说总油量不够就无解LeetCode 134题加油站环形路线每个加油站有gas[i]升油开到下一个加油站消耗cost[i]升油判断是否能绕一圈回到起点如果能则返回起点下标。这道题最反直觉的地方是它只需要一次遍历而且不回溯起点。核心逻辑是维护两个变量total记录整个环形路线的净油量总和curr记录从当前起点跑到当前位置的净油量。如果curr在某一步变成负数说明从当前起点出发到不了这个位置那么起点就要从i 1重新开始同时把curr清零。最后如果total 0说明整体油量不够返回-1否则返回起点。int canCompleteCircuit(vectorint gas, vectorint cost) { int total 0; int curr 0; int start 0; for (int i 0; i gas.size(); i) { total gas[i] - cost[i]; curr gas[i] - cost[i]; if (curr 0) { start i 1; curr 0; } } return total 0 ? -1 : start; }我第一次看这个解法的时候完全没法接受你怎么能确定从i 1开始就一定可行万一从i 1跑到后面又不行了怎么办这个疑惑的关键在于没有理解curr被清零的含义。当curr在位置i变成负数时说明从start到i之间的任意一个位置作为起点都不可能越过i这个点。这不是一个局部的结论而是一个覆盖了整个区间的结论因为从start出发到i的油量是逐步累积的如果中间某点能绕过i那curr至少不会在这一段变成负数。听起来有点绕但画一下折线图就清楚了一旦折线跌到0以下前面那段任何点作为起点最终的累计净值都会更差。这里面的巧妙之处在于贪心策略不是选择某个点作为起点而是否定掉一大批不可行的起点。每次curr 0就把start甩到i 1后面本质上是把前面所有已经验证不可行的起点一次性排除掉这是时间复杂度能做到O(n)的根本原因。3.2 分发糖果左右各扫一遍把条件拆成两个独立约束LeetCode 135题分发糖果每个孩子至少一颗相邻孩子中分数高的必须拿更多糖果问最少需要准备多少颗。这道题我第一次做的时候想用一个for循环同时判断左右两边结果越写越乱各种if嵌套最后还是错的。正确的解法是分开处理两个方向先从左往右遍历保证对于每个孩子如果他比左边孩子分数高那么他的糖果数量至少比左边孩子多一颗再从右往左遍历保证如果某个孩子比右边孩子分数高那么他的糖果数量至少要取当前值和右边孩子糖果1中的较大值。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[i 1]) { candies[i] max(candies[i], candies[i 1] 1); } } int result 0; for (int c : candies) result c; return result; }为什么要扫两遍因为比左边高和比右边高这两个约束是独立的。一次从左往右的处理只能保证满足左边方向的规则不一定满足右边方向的规则。反过来一次从右往左的处理只能满足右边方向。把两个方向各自的约束分别处理完之后再合并就不会有遗漏。这里有个细节容易忽略第二遍反向遍历时不能用candies[i] candies[i 1] 1直接赋值必须用max取较大值。因为正向遍历中已经保证了左边方向的约束如果直接覆盖可能破坏之前构建的左方向规则。我第一次做的时候在这里栽了跟头直接赋值导致中间某段孩子的糖果又不满足左边约束了。4. K次取反与局部最优的边界什么时候该停下来验证4.1 排序后优先翻转负数这是最直觉也最好用的策略LeetCode 1005题给定一个整数数组nums和一个整数k可以对同一个位置翻转符号k次求最终数组可能的最大和。这道题在训练营里算比较轻松的一道但它卡人卡在最简单的贪心判断上。最直接的想法是尽量把负数变成正数因为负数变正数收益是双倍的。要对负数下手先把数组按升序排序让绝对值最大的负数排在最前面。然后遍历数组只要k 0而且当前元素是负数就翻转它同时k--。这个过程结束后如果k还有剩余说明数组里已经没有负数可以翻了。int largestSumAfterKNegations(vectorint nums, int k) { sort(nums.begin(), nums.end()); for (int i 0; i nums.size() k 0; i) { if (nums[i] 0) { nums[i] -nums[i]; k--; } } if (k % 2 1) { auto it min_element(nums.begin(), nums.end()); *it -*it; } int result 0; for (int num : nums) result num; return result; }4.2 K还有剩余时为什么用绝对值最小的数兜底当k是奇数时多出来的翻转次数会把某个数翻回负数。为了不损失太多和应当选绝对值最小的那个数去翻。这里有个小坑min_element按数值查找如果数组里全是正数找到的最小值也就是绝对值最小的如果数组里既有正数又有负数但因为已经翻转完所有负数剩下的也都是正数所以min_element仍然能找到绝对值最小的正数。这个逻辑是自洽的。我见过有人在这道题里尝试维护一个小顶堆每次把当前最小的数翻转并放回去重复k次。这样做复杂度是O(k log n)当k很大时会超时。而排序加取模的做法是O(n log n)一个是排序成本另一个是贪心判断实际跑起来差距非常明显。4.3 这类贪心题该怎么给自己举反例K次取反这类题有个通用的验证方法试着构造一个反例看贪心策略是否会失效。例如nums [-8, -5, -3, -2, 3], k 3按排序从前往后翻负数先翻-8得8再翻-5得5再翻-3得3k用完数组变成[8, 5, 3, -2, 3]和是17。但如果先翻-5得5再翻-3得3再翻-2得2数组变成[-8, 5, 3, 2, 3]和是5明显更差。所以先翻最大绝对值负数这个局部最优确实能推出全局最优。训练营里Carl反复强调过一句话贪心策略的验证不能靠直觉要靠举反例。如果能构造出一个反例说明策略有问题如果反复尝试都构造不出来那这个策略大概率是对的。这个方法虽然不严格但在面试和刷题阶段非常实用你能快速过滤掉一大半错误的贪心方案。5. 贪心算法的证明负担以及和动态规划的交接点5.1 贪心正确性到底怎么保证这是第35天最难回答的问题之一。严格来说贪心算法的正确性需要数学证明比如交换论证法、归纳法、贪心选择性质等。LeetCode和面试中很少要求你写出完整的数学证明但面试官会追问为什么这个贪心是对的。如果你答不上来通常会被打上算法理解不深的标签。我自己的应对策略是平时刷题时多做一步反例搜索。每写完一个贪心解法都尝试构造尽可能刁钻的反例来攻击它。比如跳跃游戏II我会构造[3, 4, 3, 1, 1, 1, 1]这种数组检验贪心的区间推进思路是否依然成立。如果构造了半天找不到反例那基本可以放心。这样做久了你会有一种奇怪的直觉看到题就知道该用区间法还是排序法还是双向扫描法。5.2 训练营同伴最容易掉的三个沟通坑在训练营复盘时大家讨论比较多的问题集中在三个方面第一个坑是把贪心策略和模拟混为一谈。比如加油站那题有人会说我用两重循环模拟从每个点出发这确实能解但不叫贪心。贪心必须有一个明确的局部最优选择并且你能明确说出为什么它不会被后面的决策推翻。模拟只是暴力解法两者复杂度有本质差别。第二个坑是不会说清楚当前这一步为什么是最优。比如分发糖果有人会说先从左扫一遍再从右扫一遍但当面试官问为什么两遍就够时答不上来。正确回答思路是每个孩子的约束只有左右两个方向任意一个约束都能在单次遍历中被满足两次遍历把所有约束都覆盖了。第三个坑是做题时不当回事复盘时只看代码不重推思路。训练营第35天很多人进度一样但理解深度的差距已经拉开了。每天多花10分钟把每道题用的贪心策略用自然语言写一遍比多刷三道重复题有用得多。5.3 从Day35往后看贪心怎么为动态规划铺路第35天之后训练营就要进入动态规划了。这里有一条被很多人忽略的暗线贪心和动态规划之间不是对立的很多时候贪心是动态规划的退化版本。跳跃游戏II其实也可以用动态规划来做dp[i]表示跳到位置i的最少步数转移方程是遍历所有能到i的j取最小值加一。但这样做是O(n²)贪心直接在每一步维护全局最远可达把复杂度压到O(n)。反过来很多动态规划题目也有贪心的变体但只有特定条件下贪心才成立。比如买卖股票的最佳时机II用贪心把所有正收益都累加是因为题目允许无限次交易不存在次数限制这个动态规划的约束。如果加上交易次数限制贪心立刻失效必须上动态规划。所以第35天训练营的意义其实是在做思维切换贪心的关键是每一步做局部最优动态规划的关键是记录并合并子问题状态。这两者在某些题型上殊途同归但在约束变多时会出现明显分野。你现在把贪心的边界摸清楚后面学动态规划时就能更快地判断这道题能不能用贪心偷懒而不是每道题都硬上动态规划。写到这里我最想分享的心得是贪心是那种听懂很快、做对很难、证明最烦的算法类型。训练营到了第35天如果你跟我一样在跳跃游戏II和加油站上卡过不用怀疑智商正常现象。反过来把这些反直觉的题吃透了你后面学动态规划会轻松不少因为至少你已经建立了一个判断标准什么时候可以用局部贪心什么时候必须老老实实做状态转移。这就是第35天最大的收获不是刷了几道题而是知道了贪心这条路的边界在哪里。