LeetCode 135 分发糖果一道典型的贪心数组题。题目很短一排小朋友按顺序站着每人有一个评分值你需要准备糖果规则只有两条——每个孩子至少拿一颗糖评分比相邻孩子高的孩子拿到的糖必须比相邻的孩子多。最后要返回最少需要准备的糖果总数。题目虽小坑却不少我第一次做的时候只从左往右扫了一遍用例直接算错后来才明白这个题的“邻居约束”是双向的必须用双向贪心。这篇文章会把 LeetCode 135 的完整推导、可运行代码、三个典型用例的逐步拆解以及我实际踩过的坑一次讲清楚。无论你是刚刷题的新手还是准备面试想快速复习这篇都值得花十分钟读完。1. 题目本质与解题方向1.1 读题要抓住的三个信息先别急着写代码这道题真正想考你的不是“能不能算出来”而是“能不能看清约束的结构”。我把原题拆成三个关键信息每个孩子至少一颗糖这是底线也是所有贪心和动态规划的起点。只在相邻两个孩子之间比较评分。也就是说约束只存在于 i 和 i-1、i 和 i1 这两条边上不存在“全场最高必须拿最多”这种全局约束。这一点很重要很多人会把“评分比两个邻居都高”误解成“比所有孩子都高”。评分相等的两个相邻孩子题目没有要求糖相等。比如两个孩子评分都是 2左边可以拿 3 颗、右边可以拿 1 颗只要两边各自满足和更远邻居的约束就行。这个点最容易被忽略也是很多错误代码的来源。明确了这三条你再回头看题目会发现这就是一个“局部约束下的最小值问题”。因为约束只发生在相邻位置天然适合用贪心处理。实际推导下来贪心就是最直接的一种而且理解成本比动态规划低很多。1.2 为什么单趟扫描一定会翻车我第一次做这题的时候本能反应是从左往右扫遇到 ratings[i] ratings[i-1] 就加一颗。这个做法在递增序列上没问题但一遇到递减序列就崩了。举个最极端的例子[5, 4, 3, 2, 1]。从左往右扫每个孩子在前一个孩子的基础上都没有出现“评分变高”所以 candies 数组全是 1总和 5。但正确答案是 15因为第 0 个孩子评分 5 最高必须拿 5 颗后面依次 4、3、2、1。问题出在“评分高的孩子要比相邻孩子多”这条规则它同时看向左右两边。从左往右扫的时候你只看到了每个孩子左边的信息右边的评分完全未知。对于左边低右边高的“上坡”左到右扫描能正确处理对于左边高右边低的“下坡”左到右扫描完全无感必须从右往左再扫一遍才能补上。这其实是个很通用的直觉当约束是“双向”的时候单方向扫描只能解决一半问题。LeetCode 135 就是通过两遍扫描把双向约束拆成两个单向约束的典型例子。1.3 双向贪心约束可以拆开处理解法思路其实一句话就能说清先假设每个孩子都只有 1 颗糖然后分两趟补充。第一趟从左往右扫专门保证“如果右侧孩子评分高于左侧孩子糖数必须更多”这条规则。第二趟从右往左扫专门保证“如果左侧孩子评分高于右侧孩子糖数必须更多”这条规则。两趟都满足的位置糖果数取两趟结果里的最大值。可能你会问取 max 会不会破坏另一边已经算好的约束答案是不会。因为糖果数是一个“至少”约束只有下限没有上限。某一边要求这个孩子至少拿 3 颗另一边要求至少拿 2 颗那拿 3 颗两边都能通过。取 max 只会让数值变大而“比邻居多”这个条件在数值变大之后只会更容易成立。打个比方一个孩子既不能比左边同事工资低也不能比右边同事工资低。你从左边同事那里算出他至少该拿 5000从右边同事那边算出至少该拿 8000那就直接定 8000两边都满意。这个逻辑就是 LeetCode 135 双向贪心能够成立的根本原因。2. 两种解法双向遍历与 O(1) 单向扫描2.1 解法一双向遍历法先掌握这个双向遍历法是最容易理解、最容易写对的解法也是面试时最推荐优先给出的方案。完整步骤如下初始化 candies 数组全部置为 1满足“每个孩子至少一颗”。从左往右遍历 i 1 到 n-1如果 ratings[i] ratings[i-1]令 candies[i] candies[i-1] 1。这一步只关心左边邻居的约束。从右往左遍历 i n-2 到 0如果 ratings[i] ratings[i1]令 candies[i] max(candies[i], candies[i1] 1)。这一步只关心右边邻居的约束同时用 max 保住左边的成果。把 candies 全部加起来返回。第二步的原理很好解释如果右侧孩子评分更高那么它至少要比左侧孩子多 1 颗糖。由于初始全是 1计算 candies[i] 时 candies[i-1] 已经是满足左侧约束后的值所以在它基础上加 1 即可。连续递增的时候这个值会自然形成 1、2、3、4 的等差数列。第三步的 max 是关键中的关键。candies[i] 在第二步里可能已经因为左侧的递增链被抬得比较高比如评分序列 [1,2,3,1,2,3] 里下标 2 的孩子经过左到右扫描后已经是 3 颗。如果右到左扫描直接写成 candies[i] candies[i1] 1会把 3 覆盖成 2左边“3 必须比 2 多”的约束就被破坏了。用 max 取两者较大的那个两条规则都能保住。这套方法的时间复杂度是 O(n)空间复杂度是 O(n)因为需要额外开一个长度和 ratings 一样的数组。实际刷题和面试里这个版本绝对是首选答案。2.2 解法二常数空间单向扫描法进阶优化如果面试官紧接着问“能不能不额外开数组把空间复杂度降到 O(1)”那就需要用到下面这个进阶写法。它本质上还是贪心只是在遍历过程中用几个变量代替了 candies 数组把“上升段、平台段、下降段”分别累计。核心变量有这么几个pre当前孩子在这段“非下降状态”里应该拿到的糖数可以理解成“上一个孩子刚算完的糖数”。inc最近一次非下降段结束后峰值孩子当前的糖数也就是“当前峰高”。dec当前下降段已经走了几步也就是向下延伸的长度。ret累计答案。遍历时按三种情况处理如果 ratings[i] ratings[i-1]说明仍在上升段。pre pre 1同时让 inc pre表示峰高在抬升ret 累加 pre。如果 ratings[i] ratings[i-1]说明是平台。平台会把左右两段隔开所以 pre 重置为 1inc 也重置为 1dec 归零ret 累加 1。如果 ratings[i] ratings[i-1]说明进入下降段。dec 加 1ret 累加 dec。如果 dec 恰好等于 inc说明当前这个“峰”的两侧高度已经追平峰顶这颗糖必须再多算一颗所以先让 dec 再加 1再累加进 ret。为了说明 dec 在下降段的累计逻辑我以 [1,2,3,2,1] 为例上升段处理完后 ret 已经是 6也就是 123。进入下降段后第一个下降孩子加 1第二个下降孩子加 2最终 ret 9而正确答案正是 12321 9。每次 ret 累加 dec其实是在做两件事给新出现的坡底孩子 1 颗糖同时把已经在坡上的所有孩子各抬高 1 颗如果下降长度追平了峰高还要额外给峰顶补上 1 颗。这个解法代码更短但理解和记忆成本明显更高。第一次做这道题建议先把双向遍历法吃透O(1) 解法作为锦上添花即可。2.3 两种解法怎么选我把两种解法的特点整理成一张表方便你对照选择解法时间复杂度空间复杂度特点双向遍历O(n)O(n)思路直观、不易写错适合面试首选O(1) 单向扫描O(n)O(1)省内存但边界逻辑隐蔽适合进阶暴力回溯指数级O(n)只适合小数据对拍验证如果只是要 AC 这道题我建议直接用双向遍历法写完再顺手把 O(1) 解法当练习背下来。很多面试官会在你给出双向遍历后追问“能优化空间吗”这时候 O(1) 版本就是你亮眼的表现。3. 完整代码与案例逐步拆解3.1 可运行的完整实现先看最通用的双向遍历写法Python 版本如下def candy(ratings: list[int]) - int: n len(ratings) if n 0: return 0 candies [1] * n # 第一遍从左到右 for i in range(1, n): if ratings[i] ratings[i - 1]: candies[i] candies[i - 1] 1 # 第二遍从右到左 for i in range(n - 2, -1, -1): if ratings[i] ratings[i 1]: candies[i] max(candies[i], candies[i 1] 1) return sum(candies)注意一下如果你用的 Python 版本低于 3.9list[int] 这种类型注解会报错可以把注解去掉或者改成 from typing import List。LeetCode 环境基本都支持本地跑的话留意一下就行。再给一个 Java 版本思路完全一样import java.util.Arrays; class Solution { public int candy(int[] ratings) { int n ratings.length; int[] candies new int[n]; Arrays.fill(candies, 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] Math.max(candies[i], candies[i 1] 1); } } int total 0; for (int c : candies) total c; return total; } }C 版本也贴一份方便竞赛党直接抄#include vector #include algorithm class Solution { public: 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 total 0; for (int c : candies) total c; return total; } };最后是 O(1) 空间的进阶版本def candy(ratings: list[int]) - int: n len(ratings) if n 0: return 0 ret 1 # 第一个孩子先拿 1 颗 inc 1 # 最近一次非下降段的峰高 dec 0 # 当前下降段长度 pre 1 # 前一个孩子在非下降段的糖数 for i in range(1, n): if ratings[i] ratings[i - 1]: dec 0 pre 1 if ratings[i] ratings[i - 1] else pre 1 ret pre inc pre else: dec 1 if dec inc: dec 1 ret dec pre 1 return ret这份代码我在 LeetCode 和本地暴力对拍都跑过正确性可以放心。不过我还是那句话第一次接触这个题双向遍历永远是主答案O(1) 是加分项。3.2 案例一[1, 0, 2] 为什么结果是 5题目自带这个用例正好用来做第一个拆解。评分序列是 [1, 0, 2]三个孩子。初始 candies [1, 1, 1]。第一遍从左到右i1 时0 1 不成立什么都不改。i2 时2 0 成立candies[2] candies[1] 1 2。此时 candies [1, 1, 2]。注意这个阶段还没处理“评分 1 的孩子比评分 0 的孩子高”这件事所以下标 0 还是 1。第二遍从右到左i1 时0 2 不成立不改。i0 时1 0 成立candies[0] max(candies[0], candies[1] 1) max(1, 2) 2。最终 candies [2, 1, 2]总和 5。这个结果也符合直觉中间的孩子评分最低拿 1 颗两侧的孩子都比中间高各拿 2 颗。左右两个孩子之间不直接相邻没有约束关系所以可以拿一样多。3.3 案例二[1, 3, 2, 2, 1] 相等评分怎么处理这个用例是我自己加上去的因为它能一次性暴露两个最容易犯的错递减序列和评分相等。先看完整过程。初始 [1, 1, 1, 1, 1]第一遍从左到右步骤比较操作结果i13 1candies[1] 2[1, 2, 1, 1, 1]i22 3无[1, 2, 1, 1, 1]i32 2无[1, 2, 1, 1, 1]i41 2无[1, 2, 1, 1, 1]第二遍从右到左步骤比较操作结果i32 1candies[3] max(1, 2) 2[1, 2, 1, 2, 1]i22 2无[1, 2, 1, 2, 1]i13 2candies[1] max(2, 2) 2[1, 2, 1, 2, 1]i01 3无[1, 2, 1, 2, 1]最终 [1, 2, 1, 2, 1]总和 7。这里的关键点是下标 2 和下标 3 这两个评分都是 2 的孩子它们评分相等所以互不约束可以分别拿 1 颗和 2 颗。下标 3 拿 2 颗是因为它评分 2 大于右边的评分 1下标 2 拿 1 颗是因为它左边是 3、右边是与它相等的 2两边都不需要它更多。如果谁在代码里把“相等也强制加一”这个用例的结果就会变成 8直接被卡住。3.4 案例三第二遍扫描丢掉 max 会犯什么错我在 2.1 里提到过 max 的重要性这里用一个更直观的用例把它放大[1, 2, 3, 1, 2, 3]。第一遍从左到右后得到 [1, 2, 3, 1, 2, 3]下标 2 的孩子因为前面是 1、2 的递增链已经拿到 3 颗。第二遍从右到左时下标 2 满足 3 1会去和右边邻居比较。如果写成 candies[i] candies[i 1] 1也就是直接赋值而不取 max那么 candies[2] 会变成 candies[3] 1 1 1 2。可问题来了下标 2 评分 3 必须严格大于左边下标 1 的评分 2所以它的糖也必须严格大于 candies[1] 2。直接赋值把 3 覆盖成 2左边约束立刻被破坏。取 max 之后 candies[2] max(3, 2) 3左右两边都保住。这个用例告诉我们的经验很朴素第二遍扫描本质是在“补充”右向约束不是在“重算”所有值。只有取 max才能把第一遍的成果保留下来。3.5 边界用例速查表刷题时最怕的就是改了边界条件输出崩掉我把 LeetCode 135 题面范围内常见的边界整理成了一张速查表场景输入预期结果只有一个孩子[7]1全部评分相等[2, 2, 2, 2]4严格递增[1, 2, 3, 4]10严格递减[4, 3, 2, 1]10标准山峰[1, 2, 3, 2, 1]9递增后接平台再结束[1, 2, 2]4这些用例都可以直接跑代码验证。严格递增和严格递减的答案都是 1 2 3 4 10因为下坡时从右往左看其实也是一个递增链糖数对称。4. 常见错误、对拍验证与实战心得4.1 四个高频翻车点第一只做一趟左到右扫描。面对递减序列时结果会严重偏小上面 [5,4,3,2,1] 的例子已经足够说明问题。我见过不少人在暴力枚举阶段写对优化时反而写错就是因为贪心方向没想透。第二把相等的评分当成必须递增来处理。比如 [1,2,2] 的正确答案是 4如果你在左到右时写成大于等于就加一会得到 [1,2,3] 总和 6。记住相等评分的相邻孩子之间没有任何约束糖数完全可以是 1 和 2 甚至 1 和 5只要各自对两侧的约束成立。第三第二遍扫描直接覆盖而非取 max。这个坑在 3.4 里已经用 [1,2,3,1,2,3] 验证过属于“只在小数据上侥幸通过、大数据必挂”的典型错误。第四忘记处理 n0。题目虽然保证 n 至少是 1但如果你写通用函数给其他场景复用加上空数组判断总没有坏处。O(1) 版本里不写这个判断空数组会直接产生错误结果。4.2 用暴力回溯做对拍验证如果你刷题时想确认自己有没有写对我强烈建议写一个暴力版本做“对拍”。所谓对拍就是拿同一个输入跑两份代码一份是性能差但绝对正确的暴力解一份是你优化过的高效解随机生成大量数据后比对结果是否一致。暴力版可以直接枚举每个孩子拿几颗糖然后检查所有相邻约束。代码如下def candy_bruteforce(ratings: list[int]) - int: n len(ratings) best float(inf) candies [0] * n def check(): for i in range(n): if i 0 and ratings[i] ratings[i - 1] and candies[i] candies[i - 1]: return False if i n - 1 and ratings[i] ratings[i 1] and candies[i] candies[i 1]: return False return True def dfs(i): nonlocal best if i n: if check(): best min(best, sum(candies)) return for c in range(1, n 2): candies[i] c dfs(i 1) dfs(0) return best然后随机生成数据把两个函数一起跑import random for _ in range(200): n random.randint(1, 7) ratings [random.randint(1, 5) for _ in range(n)] assert candy(ratings) candy_bruteforce(ratings), ( ratings, candy(ratings), candy_bruteforce(ratings) )只要断言通过说明你的高效解至少在随机小数据上和行为正确的暴力解一致。这个方法在我刷算法题时救了我无数次尤其是碰到“看着简单但边界隐蔽”的题对拍比对着题解发呆高效得多。4.3 面试追问与延伸思考这题在面试里被追问的频率挺高常见的有两个方向。第一个是“能不能优化空间”。双向遍历是 O(n) 空间O(1) 的单向扫描解法就是为这个问题准备的。你可以先说双向遍历再补一句“如果要求 O(1) 空间我可以改成上升段、下降段、平台段的分段累计写法”然后现场推导一次比直接背代码更有说服力。第二个是“如果把它改成环形座位第一颗和最后一颗也算相邻呢”。环形版本需要在某个评分最低的孩子位置断开然后处理首尾相邻带来的额外约束整体思路还是这套双向贪心。不过 LeetCode 原题没有这个变体更多是面试官口头扩展考察应变能力能把线性版本讲透已经足够。给个小建议碰到这种“看解题方向比看代码量更重要”的题面试时一定要先讲思路再写代码。你把“双向约束拆成两个单向约束”这句话说出来面试官就已经知道你真的理解了。4.4 我自己的刷题复盘最后分享一点个人经验。我第一次做这道题用的是双端扫描的直觉写法但是第二遍扫描我偷懒直接赋值没有取 max结果在大数据上挂了一次。当时我还很不服气觉得取不取 max 有什么区别直到我用 [1,2,3,1,2,3] 手动演算才发现直接赋值会把第一遍辛辛苦苦累计出的递增约束抹掉。从那以后我养成了两个习惯一是遇到相邻约束的题目先判断约束是单向还是双向二是写完贪心解法后一定挑一个平台夹在上下坡之间的用例自测比如 [1,3,2,2,1] 或 [1,2,3,3,3,2,1] 这种它最容易暴露第二遍扫描中的覆盖问题。还有一个更小的细节用 Python 写这题时sum(candies) 很方便但我现在习惯在第二遍扫描结束后边循环边累加省掉一次 O(n) 遍历。LeetCode 上这两者都能通过只是能少跑一趟就少跑一趟对大数组更友好。我复盘这题时最深的体会是贪心不一定只能扫一趟。有些问题需要先做一个方向的贪心再反方向修正一遍最后合并两个结果。LeetCode 135 就是这套模板最典型的代表。把它的两遍扫描逻辑彻底吃透比你背十道简单贪心题都有用。