LeetCode 135. 分发糖果
目录
题目描述
题意分析
一排孩子站成一列，每个孩子有一个评分
ratings[i]。要给每人发糖，问在满足规则的前提下，最少一共要发多少颗。规则只有两条，但第二条藏着这道题的全部难度。第一条是每个孩子至少分到一颗糖，这给了所有位置一个下界
1。第二条是「相邻的两个孩子中，评分更高的那个必须拿到更多糖果」——注意它说的是「相邻两个」，而不是「比左边的多」。这意味着对位置i来说，它同时被左右两个邻居约束：如果ratings[i] > ratings[i - 1]，那么candies[i] > candies[i - 1]；如果ratings[i] > ratings[i + 1]，那么candies[i] > candies[i + 1]。这是一个双向约束，而不是单向的递推关系，读题时如果把它当成「从左往右越来越高就越给越多」，后面必然出错。反过来说，评分相等时规则不生效。
ratings[i] == ratings[i - 1]时两人可以拿一样多，甚至可以一个多一个少，规则对相等的情况完全没有要求。这一点是很多贪心题里最省糖的地方，也是最容易被误加约束的地方。边界方面：数组长度至少为 1，单个孩子直接返回 1；评分可以完全相同，此时答案就是
n；评分可以单调递增或单调递减，这两种极端形态会让某一趟扫描把整条链都串起来，是验证代码的好用例。题目求的是「最少」，所以每个位置都应该压到它的约束允许的最小值，多给一颗就不是最优解。
解法：左右两次扫描取最大约束
核心思路
问题关键：每个孩子同时受左右邻居约束。只从左向右扫描能保证“评分高于左邻居时糖更多”，却无法保证下降段中的右侧约束；反向扫描同理，所以一趟贪心信息不足。
为什么选两次扫描：先把每人初始化为 1。第一趟从左到右处理所有上升关系；第二趟从右到左处理所有下降关系。第二趟使用
max(当前值, 右邻居+1)，在补足右约束时保留第一趟已经建立的左约束。状态与不变量：第一趟结束后，
candies[i]是仅考虑左邻居时的最小合法值。第二趟扫描到 i 时，candies[i+1]已满足两侧约束；更新后的candies[i]同时不小于左右两个方向要求的下界。正确性：设只考虑左、右邻居时的最小值分别为
L[i]、R[i]，任何合法方案都必须满足candy[i] ≥ L[i]且candy[i] ≥ R[i]，所以至少为max(L[i],R[i])。两趟扫描恰好得到这个最大值，它同时满足两侧约束，因此逐位置都不能再减少，总和就是全局最小。
解题步骤
- 创建
candies并全部填 1，落实每个孩子的最低糖果数。- 从左到右：若当前评分更高，令当前糖果为左邻居加 1。
- 从右到左：若当前评分更高，令当前糖果为“原值”和“右邻居加 1”的较大者。
- 累加
candies得到最少总数；评分相等时两趟都不更新。- 口述样例：
[1,0,2]初始化为[1,1,1]，左扫得到[1,1,2]，右扫补成[2,1,2]，答案为 5。[1,2,2]得到[1,2,1]，说明相等评分不要求糖果递增。
代码实现
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 ans = 0;
for (int candy : candies) {
ans += candy;
}
return ans;
}
}
func candy(ratings []int) int {
n := len(ratings)
candies := make([]int, n)
for i := 0; i < n; i++ {
candies[i] = 1
}
for i := 1; i < n; i++ {
if ratings[i] > ratings[i-1] {
candies[i] = candies[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if ratings[i] > ratings[i+1] {
needed := candies[i+1] + 1
if candies[i] < needed {
candies[i] = needed
}
}
}
ans := 0
for _, candy := range candies {
ans += candy
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，两次扫描和一次求和都为线性时间。
- 空间复杂度：$O(n)$，使用一个与评分数组等长的糖果数组。
关键点总结
- 双向局部约束可以拆成两次相反方向的单向传播。
- 第二趟必须取最大值，不能覆盖第一趟形成的左侧约束。
- 只有评分严格更高才增加糖果；相等评分没有大小要求。
- 面试追问 $O(1)$ 空间时，可按连续上升、下降段计数并用等差数列求和；主解法优先保证清晰和稳定。
易错点总结
- 只做左扫描：
[1,0,2]会得到[1,1,2]，位置 0 未满足右侧约束。- 右扫描直接覆盖：
[1,2,3,1]会把峰值 3 降成 2，破坏已满足的左侧约束。- 右扫描方向写反：长下降段依赖右邻居的最终值，必须从右向左传播。
- 数组未初始化为 1：全相等输入会错误返回 0，而每个孩子至少需要一颗。
- 比较使用
>=：[1,1,1]会被多发糖果；评分相等时规则不生效。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 238. 除了自身以外数组的乘积 | 中等 | 同样是左右两趟，但合并方式是相乘而非取 max |
| 42. 接雨水 | 困难 | 双向扫描求左右最大值，合并时取的是较小者 |
| 55. 跳跃游戏 | 中等 | 单向贪心即可，维护能到达的最远边界 |
| 45. 跳跃游戏 II | 中等 | 贪心分层，按当前层的右边界切分步数 |
| 763. 划分字母区间 | 中等 | 先预处理末次位置，再一趟扫描确定切分点 |
| 406. 根据身高重建队列 | 中等 | 贪心的关键在排序顺序，插入时才满足计数约束 |