LeetCode 135. 分发糖果 算法题解
题目描述
n 个孩子站成一排，给定数组 ratings 表示每个孩子的评分。需要分发糖果，满足：
- 每个孩子至少分到 1 个糖果
- 相邻两个孩子中，评分更高的获得更多糖果
返回所需的最少糖果总数。
题目理解与关键点
- 约束是相邻比较，只有两个方向：左邻居、右邻居
- 评分相等时没有约束，可以分同样多的糖果（不要求更高）
- 求的是最小值，所以每个孩子应该在满足约束的前提下尽量拿少的糖
核心思路：贪心 + 两次遍历
为什么不能一次遍历？
因为每个孩子同时受左右两个邻居的影响，而一次遍历只能保证一个方向。
只从左到右： 只能保证"右边比左边评分高的孩子糖多"，处理不了"左边比右边评分高的"情况。
反例： ratings = [2, 1, 2]（中间是谷底，两侧都更高）
只从左到右: 初始: [1, 1, 1] i=1: ratings[1]=1 < ratings[0]=2，不改 i=2: ratings[2]=2 > ratings[1]=1，加糖 → [1, 1, 2] 结果: [1, 1, 2] ← 错误！孩子0评分最高却只拿1个
孩子0是"左边比右边高"，这个方向被漏掉了，必须从右到左再处理一遍。
算法流程
- 初始化：所有孩子先分 1 个糖（满足约束1）
- 第一遍（从左到右）：处理"右边评分高"的情况
如果 ratings[i] > ratings[i-1]： candle[i] = candle[i-1] + 1
保证每个孩子的糖比左边评分低的邻居多
- 第二遍（从右到左）：处理"左边评分高"的情况
如果 ratings[i] > ratings[i+1]： candle[i] = max(candle[i], candle[i+1] + 1)
保证每个孩子的糖比右边评分低的邻居多，用 max 同时满足两个方向
- 求和：返回所有糖果总数
为什么第二遍用 max？
一个孩子可能同时比左右都高（山峰），两边都会给他一个"最少要求值"。取 max 保证同时满足两个方向的约束，且不再增大（因为其他位置不受影响）。
逐步演示
ratings = [1, 0, 2]
初始: [1, 1, 1] 左→右: i=1: ratings[1]=0 < ratings[0]=1，不改 → [1, 1, 1] i=2: ratings[2]=2 > ratings[1]=0，加糖 → [1, 1, 2] 右→左: i=1: ratings[1]=0 < ratings[2]=2，不改 → [1, 1, 2]
总和 = 1 + 1 + 2 = 4 ✓
验证：0号(评1)比1号(评0)高 → 1>1？不对，0号1个、1号1个，但评分1>0需要0号更多，有误？
（纠正）正确演示 ratings = [0, 1, 2] 或 ratings = [1, 2, 2]：
ratings = [1, 2, 2]
初始: [1, 1, 1] 左→右: i=1: ratings[1]=2 > ratings[0]=1 → [1, 2, 1] i=2: ratings[2]=2 == ratings[1]=2，不改 → [1, 2, 1] 右→左: i=1: ratings[1]=2 == ratings[2]=2，不改 → [1, 2, 1]
总和 = 1 + 2 + 1 = 4 ✓
代码实现
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candle(n, 1); // 每人至少 1 个
// 从左到右：保证右边评分高的糖比左边多
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candle[i] = candle[i - 1] + 1;
}
}
// 从右到左：保证左边评分高的糖比右边多
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candle[i] = max(candle[i], candle[i + 1] + 1);
}
}
int sum = 0;
for (int c : candle) {
sum += c;
}
return sum;
}
};
复杂度分析:
时间复杂度：O(n)，两次线性遍历 + 一次求和
空间复杂度：O(n)，candle 数组存储每个孩子的糖果数