LeetCode 135困难贪心 · 双向扫描
分发糖果 图解题解
这道题到底在问什么
ratings[i] 是第 i 个孩子的评分。每个孩子至少 1 颗糖；相邻孩子里，评分更高的那个糖必须更多（只看左右相邻，不跨人比）。求最少需要多少颗糖。
- 输入
- ratings=[1,0,2]
- 输出
- 5 （分别发 2,1,2 颗）
- 输入
- ratings=[1,2,2]
- 输出
- 4 （分别发 1,2,1 颗；后两人评分相等，不要求谁多）
最优解：一步一步想明白
- 3记住这条「左右各扫一遍、每位取两遍最大」，下面每一帧都在套它。
- 4上面这行是每个孩子的评分（长度固定）。先满足「每人至少 1 颗」，给所有人都发 1 颗——这是 RESULT 里 candy 数组的起点，接下来两遍扫描会把该加的加上去。
- 5第一遍从左往右，看孩子 0。最左孩子没有左邻，保持 1 颗。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 6第一遍从左往右，看孩子 1。ratings[1]=3 > ratings[0]=1（右高于左）→ candy[1]=candy[0]+1=2。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 7第一遍从左往右，看孩子 2。ratings[2]=4 > ratings[1]=3（右高于左）→ candy[2]=candy[1]+1=3。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 8第一遍从左往右，看孩子 3。ratings[3]=5 > ratings[2]=4（右高于左）→ candy[3]=candy[2]+1=4。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 9第一遍从左往右，看孩子 4。ratings[4]=2 ≤ ratings[3]=5（不比左邻高）→ 维持 candy[4]=1。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 10第一遍从左往右，看孩子 5。ratings[5]=1 ≤ ratings[4]=2（不比左邻高）→ 维持 candy[5]=1。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 11第一遍从左往右，看孩子 6。ratings[6]=3 > ratings[5]=1（右高于左）→ candy[6]=candy[5]+1=2。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 12第一遍从左往右，看孩子 7。ratings[7]=2 ≤ ratings[6]=3（不比左邻高）→ 维持 candy[7]=1。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 13第一遍从左往右，看孩子 8。ratings[8]=1 ≤ ratings[7]=2（不比左邻高）→ 维持 candy[8]=1。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 14第一遍从左往右，看孩子 9。ratings[9]=6 > ratings[8]=1（右高于左）→ candy[9]=candy[8]+1=2。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 15第一遍从左往右，看孩子 10。ratings[10]=5 ≤ ratings[9]=6（不比左邻高）→ 维持 candy[10]=1。这一遍只管「右边评分更高的要比它左边糖多」这一个方向。
- 16第一遍扫完。此时每个「比左邻评分高」的孩子都已经比左邻糖多了。但「比右邻评分高」的孩子（处在下坡段）还没被照顾——下面第二遍从右往左补。
- 17第二遍从右往左，看孩子 10。最右孩子没有右邻，保持当前糖数不变。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 18第二遍从右往左，看孩子 9。ratings[9]=6 > ratings[10]=5，但 candy[9]=2 已≥candy[10]+1=2，取 max 后不变。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 19第二遍从右往左，看孩子 8。ratings[8]=1 ≤ ratings[9]=6（不比右邻高）→ 维持 candy[8]=1。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 20第二遍从右往左，看孩子 7。ratings[7]=2 > ratings[8]=1（左高于右）→ candy[7]=max(2, candy[8]+1)=2。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 21第二遍从右往左，看孩子 6。ratings[6]=3 > ratings[7]=2（左高于右）→ candy[6]=max(3, candy[7]+1)=3。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 22第二遍从右往左，看孩子 5。ratings[5]=1 ≤ ratings[6]=3（不比右邻高）→ 维持 candy[5]=1。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 23第二遍从右往左，看孩子 4。ratings[4]=2 > ratings[5]=1（左高于右）→ candy[4]=max(2, candy[5]+1)=2。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 24第二遍从右往左，看孩子 3。ratings[3]=5 > ratings[4]=2，但 candy[3]=4 已≥candy[4]+1=3，取 max 后不变。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 25第二遍从右往左，看孩子 2。ratings[2]=4 ≤ ratings[3]=5（不比右邻高）→ 维持 candy[2]=3。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 26第二遍从右往左，看孩子 1。ratings[1]=3 ≤ ratings[2]=4（不比右邻高）→ 维持 candy[1]=2。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 27第二遍从右往左，看孩子 0。ratings[0]=1 ≤ ratings[1]=3（不比右邻高）→ 维持 candy[0]=1。取 max 很关键：既照顾「左边评分更高要比右边糖多」，又不破坏第一遍已满足的左邻约束。
- 28两遍都扫完。每个孩子取了两遍里的更大值，左右相邻约束同时满足，且每步只在必须时才 +1，所以这就是最少的发法：总共 22 颗。
⚠️ 容易写错的地方
✗ 错：第二遍直接赋值 candy[i]=candy[i+1]+1
✓ 对：必须 candy[i]=max(candy[i], candy[i+1]+1)
直接赋值会覆盖掉第一遍已满足的左邻约束，导致左边那对又不成立
✗ 错：只扫一遍就返回
✓ 对：必须左右各一遍
一遍只能保证一个方向（如只保证右高于左），下坡段的左高于右没被照顾
✗ 错：评分相等也强行 +1
✓ 对：只有「严格大于」才要求糖更多
题目规定相等时两人之间无约束，强行 +1 会多发糖、不再是最少
完整代码（Python / C++ / Java）
Python
def candy(ratings):
n = len(ratings)
c = [1] * n # ① 每人至少 1 颗
for i in range(1, n): # 第一遍 左→右
if ratings[i] > ratings[i-1]:
c[i] = c[i-1] + 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) # 取 max 不破坏左邻约束
return sum(c)C++
int candy(vector<int>& ratings){
int n = ratings.size();
vector<int> 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;
}Java
public int candy(int[] ratings) {
int n = ratings.length;
int[] c = new int[n];
Arrays.fill(c, 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] = Math.max(c[i], c[i + 1] + 1);
int sum = 0;
for (int x : c) sum += x; // 求和
return sum;
}复杂度
时间
O(n)
左右各扫一遍数组，共 2n 步
空间
O(n)
一个 candy 数组记录每个孩子的糖数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 分发糖果 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能只用 O(1) 额外空间做？+
能。把序列看成若干「上坡段」和「下坡段」，统计上坡长度 up、下坡长度 down 和峰顶糖数，按段贡献糖数累加即可，不需要 candy 数组。但两遍扫描写法更直观、最常用、也最不易错，面试里先答它再提 O(1) 优化。
为什么两遍贪心能保证总数最少？+
每个位置的糖数 = 它被左右两个方向「逼」出来的最小值。左→右给出满足左约束的最小值，右→左在不破坏左约束的前提下补足右约束（取 max）。每一步都只在「必须 +1」时才加，没有任何一颗糖是多发的，所以全局最少。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 分发糖果 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。