糖果这个标题刚弹出来的时候,我脑子里第一时间跳出来的就是LeetCode 135那道经典题——分发糖果。再配上贪心这个标签,基本可以确定:这又是一道让无数人在面试和刷题路上栽过跟头的贪心算法题。说实话,这道题我前前后后刷过好几遍,每次以为自己彻底搞懂了,过段时间再看到还是能琢磨出点新东西。它表面上只是个发糖果的小场景,实际上把贪心算法的适用边界、局部最优和全局最优的关系、双方向约束的处理手法全给揉进去了,还顺便能和跳跃游戏II这种覆盖面型贪心构成一组很好的对照组。这篇文章我不打算只贴一份AC代码就完事。我会把这道题从题意拆解、两次遍历的贪心原理、三种写法(两遍扫描、常数空间优化、分组视角)一直讲到位,然后拉上跳跃游戏II做横向对比,最后把我踩过的坑和面试讲解技巧一并交代清楚。刷过这题的人可以从里面捞点不一样的视角,没刷过的人跟着走一遍也能把贪心这个专题的地基打牢。1. 题目到底在说什么:读懂糖果这道题先花点时间把题目精读一遍。力扣上的原题编号是135,英文名Candy,国内一般叫分发糖果或者糖果。题目设定很简单,N个孩子排成一排,每个孩子有一个评分数组ratings,你需要按照两条规则给孩子们发糖果:每个孩子至少分到1颗糖果;相邻两个孩子中,评分更高的那个必须比评分低(或相等)的那个拿到更多糖果。题目要求返回你最少需要准备多少颗糖果。注意第二条规则的准确含义:它只说评分更高的孩子要比评分更低的邻居拿得多,评分相同的时候没有任何约束。我在刚开始刷这题的时候就在这里吃过亏,下意识认为相邻且相等也得给不同数量的糖果,导致用[1, 2, 2]这个用例去验证时,算出5颗,而正确答案是4颗。原因很简单,第二个孩子评分是2,第三个孩子评分也是2,评分相等,第三个孩子拿1颗完全合法。这个题为什么和贪心绑定在一起?因为你要全局糖果数最少,本质上是在每个孩子身上分配一个尽量小的值,而这个值同时受左右两个方向的约束牵制。如果只是单方向(比如只要求左边的孩子评分高就必须多拿),那直接一趟从左到右扫过去就行,每一步只看前一个孩子,这本身就是一个典型的局部最优叠加成全局最优的贪心过程。难就难在约束是双向的,一个孩子既可能被左侧约束,也可能被右侧约束,两边都压着的时候,你得取两边约束中更严格的那个。还有一点值得注意,这道题的正确性从数学上还可以用每个孩子的糖果数 max(左侧连续上升长度, 右侧连续下降长度) 1来刻画,这为后面几种优化写法埋下了伏笔。这个视角非常重要,它把代码里两个for循环的为什么要做、为什么这么写,彻底讲透了。2. 贪心思路拆解:为什么要从左到右再从右到左2.1 先做一次方向明确的贪心试点我拿一个具体例子说明。假设评分是[1, 3, 2, 1],正确分配应该是[1, 2, 2, 1]吗?不是。你手动推一下:第1个孩子拿1颗;第2个孩子评分3比第1个孩子高,至少要2颗;第3个孩子评分2比第2个孩子低,但比第4个孩子评分1高,所以第3个孩子必须比第4个多,而第4个至少1颗,于是第3个孩子至少2颗;再看第2个孩子评分3比第3个孩子评分2高,第2个孩子必须比第3个多,那第2个孩子就得是3颗。正确答案是[1, 3, 2, 1],总数7。从这个过程能发现一个规律:一个孩子最终能拿到的糖果数,取决于他在左侧递增视角下的位置,以及他在右侧递减视角下的位置,两者取较大值。第1个孩子在两侧都不形成压力,所以是1;第2个孩子在递增链里是第2个,在递减链里也是最高点,两个方向都要求他多拿;第3个孩子在递增视角下是谷底,但在递减视角下比第4个高,所以被右侧约束顶到2。这就是从左到右贪心一次,从右到左贪心一次的直觉来源。从左往右扫,能保证当前孩子比左边孩子评分高时,糖果数一定比左边多;但这个保证是单向的,它没有任何能力去处理当前孩子比右边孩子评分高的场景。比如[1, 3, 2, 1],只做从左到右,得到的糖果数组是[1, 2, 1, 1],第3个孩子在这里拿了1颗,但第4个孩子也是1颗,第3个孩子明明评分更高却和第4个拿得一样多,违反规则。所以必须再从右往左扫一边,把右侧约束补上。2.2 两次贪心叠加之后,为什么一定是全局最优有人会问:两次都只做局部调整,一个从左一个从右,加起来就能保证全局最优吗?这里需要从数学上稍微说透一点。设第i个孩子的最终糖果数为c[i]。第一次从左到右后,c[i]至少满足ratings[i] ratings[i-1]时,c[i] c[i-1]。第二次从右到左,用c[i] max(c[i], c[i1] 1)的方式更新,所以等式两边的最优性都是保住的:左边的约束不会被破坏,因为max操作只会把值变大,而变大不会让比左边多这个条件失效;右边的约束则通过这一轮补齐。换句话说,第一个for循环保证了所有右坡约束(右边的孩子比左边高)成立,第二个for循环保证了所有左坡约束(左边的孩子比右边高)成立。由于任意一对相邻关系,要么属于左坡,要么属于右坡,要么两者都不属于(评分相等),所以最终所有相邻约束全部满足,且每一步都只取满足约束的最小增量,总和就是最小的。这个分方向处理双向约束的手法,在后续很多区间类、峰值类问题里都能复用。我个人的感受是,不要试图一次性同时满足两个方向,那样脑子会绕晕。把双向约束拆成两个单向约束,先修一个方向,再修另一个方向,是贪心题里一个非常好用的套路。3. 完整实现:代码、复杂度与三种典型解法3.1 基础版:两次遍历 糖果数组,空间O(n)先把最通用、也最不容易出错的版本贴出来。这个版本我用C写,逻辑清晰,方便解释:int candy(vectorint ratings) { int n ratings.size(); vectorint c(n, 1); // 每个孩子至少1颗 // 第一遍:从左到右,保证评分比左边高时,糖果比左边多 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { c[i] c[i - 1] 1; } } // 第二遍:从右到左,保证评分比右边高时,糖果比右边多 for (int i n - 2; i 0; i--) { if (ratings[i] ratings[i 1]) { c[i] max(c[i], c[i 1] 1); } } int sum 0; for (int x : c) sum x; return sum; }第一步初始化成1是必须的,每个孩子至少一颗这个底线先铺平。第一遍循环从1开始,把每个右坡填平。第二遍循环从n-2开始,处理左坡,这里用的是max(c[i], c[i1]1)而不是直接c[i] c[i1]1,这是全题最容易写错的一个点。如果你直接赋值,左边约束已经给到的较大值可能被右边的较小要求覆盖掉。比如评分[1, 3, 2, 1],第一遍后c [1, 2, 1, 1],第二遍时i 2,c[2] max(1, 2) 2没问题;但假设某种情况下第一遍算出中间值是4,右侧只需要2,直接赋值会把4改成2,左边约束就崩了。所以这个max不是可有可无的铠甲,它是两次贪心叠加的关键粘合剂。时间上,三次线性遍历,复杂度O(n);空间上多开了一个长度为n的数组,O(n)。3.2 进阶版:分段统计,把空间压到O(1)两遍扫描版本已经足以通过所有数据,不过还有更省空间的常数空间写法。思路是把评分序列看成由若干严格递增段和严格递减段拼接而成,然后对每一段分别处理。这个写法的思路如下:从左到右遍历,维护当前孩子拿到的糖果数pre,以及当前递增段的长度inc、递减段的长度dec;如果当前评分比前一个大,说明处于递增段,pre(当前孩子至少比前一个多1),inc pre,dec 0;如果当前评分和前一个相等,pre 1,inc dec 0(相等时没有约束,只给1颗);如果当前评分比前一个小,说明处于递减段,dec;如果dec inc,说明下降段的长度追上了上升段的峰值高度,需要把峰值孩子(也就是上升段最后那个)的糖果数也加1,所以总糖果数res,pre 1;每次遍历完一个孩子,把pre累加到总和中。完整代码:int candy(vectorint ratings) { int n ratings.size(); if (n 1) return 1; int res 1; // 第一个孩子先发1颗 int pre 1; // 前一个孩子的糖果数 int inc 1; // 当前递增段长度 int dec 0; // 当前递减段长度 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { pre; res pre; inc pre; dec 0; } else if (ratings[i] ratings[i - 1]) { pre 1; res pre; inc dec 0; } else { dec; if (dec inc) dec; res dec; pre 1; } } return res; }这个版本的关键在于if (dec inc)这个判断。假设上升段已经累积到inc 3,紧接着来了三个下降点,递减段长度到3时,峰值孩子(就是上升段最后一个,同时也是递减段第一个)必须比递减段里所有孩子都多,此时需要给这个峰值孩子额外加1颗,用dec来补上这个增量。这里我把代码稍微简化处理了,具体实现时不同人的写法略有差异,但核心思路完全一致。空间上只需要几个整数变量,O(1);时间还是O(n)。这个写法的缺点是边界情况比较多,不太好记,容易在细节上出错。我建议你面试时优先写两遍扫描版本,常数空间版本当作有余力时的加分项去准备,真要写也需要先在纸上推两个例子再动键盘。3.3 Python版实现:日常刷题和面试同样够用Python版本的思路和C完全一致,代码看起来更紧凑:def candy(ratings): n len(ratings) c [1] * n for i in range(1, n): if ratings[i] ratings[i - 1]: c[i] c[i - 1] 1 for i in range(n - 2, -1, -1): if ratings[i] ratings[i 1]: c[i] max(c[i], c[i 1] 1) return sum(c)3.4 边界用例自测清单写完代码一定要拿这几组边界用例测试,它们几乎覆盖了所有易错场景:输入ratings正确输出说明[1]1只有一个孩子,直接给1颗[1, 2, 2]4评分相同的邻居之间没有约束,答案是[1, 2, 1][2, 2, 2]3全部相等,每人1颗[1, 2, 3, 4]10严格递增,等差数列1234[4, 3, 2, 1]10严格递减,同样等差数列[1, 3, 2, 1]7峰值在中间,峰值要求最高,答案为[1, 3, 2, 1][1, 2, 3, 1, 2]?混合增减,建议手动推一遍再对答案最后一行留了个思考题,我的答案是[1, 2, 3, 1, 2],总和9。你推的时候注意第二个1右侧还有上升,所以第4个孩子在这里是1颗而不是从头开始累积,推完你就能加深对每个孩子在两个方向各自的位置的理解。4. 和跳跃游戏II联动:贪心算法在序列题中的两种典型模式4.1 跳跃游戏II:贪心的另一张脸看到热搜词里的跳跃游戏2 贪心算法,干脆把这道姊妹题也一起拿出来盘一盘。跳跃游戏II的问题是:给你一个非负整数数组nums,你初始在下标0位置,数组里每个元素代表你最多能往后跳多远,问最少跳几次能到达数组最后一位。这道题的贪心策略非常典型:你在当前位置能跳到的范围内,选择下一跳能覆盖得更远的那个位置。每一步都让下一步的可达范围尽可能大,局部最优叠加出来就是全局的跳跃次数最少。实现上我习惯维护两个变量:cur:当前这一跳能到达的最远下标;next:在cur范围内遍历所有点时,计算得到的下一步最远可达下标。每遍历到一个新位置,先用i nums[i]更新next;当i走到cur时,说明当前这一跳已经到极限了,把cur更新成next,跳跃次数加1。代码长这样:int jump(vectorint nums) { int n nums.size(); if (n 1) return 0; int ans 0, cur 0, next 0; for (int i 0; i n - 1; i) { next max(next, i nums[i]); if (i cur) { cur next; ans; } } return ans; }注意循环只到n - 2,因为最后一个位置不需要再跳。i cur的判断是整个代码的节拍器,它标记了这一跳覆盖区间的右端点。区间内的每个位置都被视作潜在起跳点,能到的最远距离不断冲刷next,到达右端点时下一条命就续上了。这也是贪心里很经典的覆盖区间推进模式。4.2 两种贪心模式:约束型贪心 vs 覆盖型贪心把糖果和跳跃游戏II摆在一起看,能明显看出贪心算法在序列题里的两条分支:糖果题属于约束型贪心:每个位置的结果受邻居约束,你需要把每个方向的约束拆开、逐个方向满足,然后用max合成最终答案。核心操作是分方向处理 取严格值。跳跃游戏II属于覆盖型贪心:每个位置都能扩展出一个可达范围,你需要不断用max扩大覆盖边界,边界走到头时触发一次决策。核心操作是范围扩展 边界触发。两者都满足贪心算法的两大前提:贪心选择性质和最优子结构。具体到这两个题,每一次局部决策都不影响后续决策的独立性和整体最优性——糖果题里,无论先从左扫还是先从右扫,另一方向的约束都能独立补上;跳跃游戏II里,每次选择能跳最远的点,不会改变后续其他点是否可达的性质。这也是为什么它们能被冠以贪心而不是动态规划的原因:动态规划通常需要枚举所有子问题的组合才能取最优,而这两道题只在局部做一次决策就行。如果你刷题时正在准备面试,我强烈建议把这两题当成一组对照题一起整理进自己的笔记:糖果讲的是双向约束如何拆解,跳跃游戏讲的是区间覆盖如何推进。这两个套路分别掌握之后,很多中间难度的贪心题都能往这两个盒子里装。5. 踩坑记录:这题最常见的几个错误这部分是我在刷题群、面试复盘、还有自己重刷时总结出来的高频犯错点,逐个列出来给大家避雷。错误一:只做一次从左到右的遍历。不少第一次接触这题的人会写完第一遍循环就直接返回sum,遇到[1, 3, 2, 1]这种右侧存在下降趋势的数据就挂了。原因前面已经分析过:单方向遍历只能覆盖一半的相邻约束。判断自己是不是只写了一边,就用一个右侧明显有递减的用例去试。错误二:第二遍循环用直接赋值而不是取max。这是我最爱考别人的一个细节。在从右往左扫时,如果写成c[i] c[i 1] 1,会覆盖第一遍循环已经得到的较大值。记住:max的作用是在满足右侧约束的同时,不破坏左侧约束已经生效的结果。想记住这个点,就反复念叨一句话:第二次贪心的目标是补约束,不是重新分配。错误三:忽略了评分相等的场景。题目对评分相等的相邻孩子没有任何数量要求,所以相等时只能让后面的孩子回到1颗,不能继续累加。这个坑在[1, 2, 2, 3]这类用例上炸过一次后就会长记性,正确分配是[1, 2, 1, 2],总共6颗,很多新手会算成7。错误四:初始化全为0而不是1。有些版本一开始把所有c[i]初始化为0,后面再用c[i] 1之类的逻辑去补齐,边界条件一多就容易漏。不如直接从每人1颗出发,把底薪先发到位,后面只处理增量。这样代码更稳,解释起来也更顺畅。把上面四个错误整理成一张问题速查表:易错点错误表现正确做法忽略第二遍扫描评分递减场景算错左右各扫一遍,双向约束都补齐第二遍直接赋值左坡约束被覆盖用c[i] max(c[i], c[i1]1)评分相等时没重置[1,2,2]算出5相等时当前孩子拿1颗,不累加初始化不是1边界易漏、解释困难初始化c [1] * n,先发底薪6. 面试现场:这题怎么讲才能拿高分最后分享点面试实战经验。糖果这道题在面试中的出现频率非常高,基本是贪心入门三件套之一(另外两个是跳跃游戏、加油站)。面试官让你做这题,考察的其实不只是会不会写代码,而是你能不能把双向约束这个难点讲清楚。我的建议是,拿到题后先别急着写代码,先用一个手动例子演示你的思考过程。你可以说:我先尝试只从左往右扫一遍,发现右边下降的情况处理不了,于是我从右往左再扫一遍,每次用max把两边约束结合。这句话一说出口,面试官就知道你是在真正分析问题,而不是背模板。紧接着你在纸上写出[1, 3, 2, 1]的推导过程,展示第二遍循环前后的数组变化,这比任何口头解释都更有说服力。如果面试官追问能不能优化空间,你可以把O(1)的分段写法思路讲出来,不一定要现场写完整,但至少要把上升段正常累加,下降段用等差数列求和或者递减计数器处理,当递减长度追上上升峰值时给峰值补发一颗这个逻辑说清楚。能讲到这一层,基本证明你对题目的理解已经超过大多数候选人了。还有个小技巧:写完代码后主动说一句我会用[1,2,2]和[1,3,2,1]这两个用例自查一下,然后快速在脑子里过一遍结果。这种行为会给人留下训练有素、有工程习惯的印象,比解完题就干坐着等下一题要加分得多。至于刷题训练的建议,我的心得是:贪心算法不能靠死记硬背,必须建立局部最优为什么会等于全局最优的直觉。每次遇到一个贪心题,先问自己三个问题——这个问题的约束是什么方向?局部决策是什么?这个决策会不会影响后续决策?糖果题的答案是约束是双向的,局部决策是取满足约束的最小增量,不会影响其他节点的独立约束,跳跃游戏II的答案是约束是单向覆盖,局部决策是选覆盖最远的点,不会影响可达性。这三个问题回答清楚了,贪心题基本就稳了。