贪心算法专题(九)：左顾右盼太累，不如分头行动——「分发糖果」
哈喽各位，我是前端小L。
欢迎来到贪心算法专题第九篇！ 小时候排排坐分果果，老师总是说“表现好的要多给”。今天这道题就是把这个场景算法化了。（后续代码示例都改为javascript，助力前端面试）
规则：
每个孩子至少分配到1个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
难点：“相邻”意味着既要看左边，又要看右边。 比如[1, 3, 2]：
中间的
3比左边1大，所以糖果要比左边多。中间的
3比右边2大，所以糖果也要比右边多。 如果我们同时考虑两边，很容易把自己绕进去。
力扣 135. 分发糖果
https://leetcode.cn/problems/candy/
题目分析：
输入：
ratings数组。输出：最少需要的糖果总量。
例子：[1, 0, 2]
分发：
[2, 1, 2]解释：中间的
0必须有 1 个。左边的1比0高，所以给 2 个。右边的2比0高，也给 2 个。总共 5 个。
核心思维：两次贪心 (Two-Pass Greedy)
既然同时考虑左右两边很难，那我们就把规则拆开，一次只考虑一边！
第一步：只看左边 (Left to Right)
规则：只要
ratings[i] > ratings[i-1]，那么candies[i]就必须比candies[i-1]多一个。操作：从左往右遍历。如果评分涨了，糖果就在前一个人的基础上
+1；否则（评分降了或相等），只给保底的1个。
第二步：只看右边 (Right to Left)
规则：只要
ratings[i] > ratings[i+1]，那么candies[i]就必须比candies[i+1]多一个。操作：从右往左遍历。
关键冲突解决： 当我们从右往左遍历时，发现
ratings[i] > ratings[i+1]，我们本来想把candies[i]设为candies[i+1] + 1。 但是！candies[i]在第一步中已经有了一个数值（为了满足左边规则）。贪心策略：为了同时满足左边和右边的规则，我们取最大值。 即：candies[i] = Math.max(candies[i], candies[i+1] + 1)。
算法流程
初始化：创建一个长度为
n的数组candies，默认全部填充1（每人至少一个）。左 -> 右遍历：
for (let i = 1; i < n; i++)如果
ratings[i] > ratings[i-1]，则candies[i] = candies[i-1] + 1。
右 -> 左遍历：
for (let i = n - 2; i >= 0; i--)如果
ratings[i] > ratings[i+1]，则candies[i] = Math.max(candies[i], candies[i+1] + 1)。
求和：把
candies数组里的数加起来。
代码实现 (JavaScript)
JavaScript
/** * @param {number[]} ratings * @return {number} */ var candy = function(ratings) { let n = ratings.length; // 每个人至少一个糖果 let candies = new Array(n).fill(1); // 1. 先从左往右遍历 (只比较左边的孩子) // 策略：如果右边评分比左边高，糖果 = 左边 + 1 for (let i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } // 2. 再从右往左遍历 (只比较右边的孩子) // 策略：如果左边评分比右边高，糖果 = max(当前值, 右边 + 1) // 注意：倒序遍历，从倒数第二个开始 for (let i = n - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { // 为什么要取 max？ // candies[i] 目前的值是满足了“左规则”的 // candies[i+1] + 1 是为了满足“右规则”的 // 要想同时满足左右，必须取两者中较大的那个 candies[i] = Math.max(candies[i], candies[i + 1] + 1); } } // 3. 统计总数 let sum = 0; for (let i = 0; i < n; i++) { sum += candies[i]; } return sum; };深度图解 (脑补)
假设ratings = [1, 3, 4, 5, 2]
初始状态：
[1, 1, 1, 1, 1]左 -> 右：
3>1:
[1, 2, 1, 1, 1]4>3:
[1, 2, 3, 1, 1]5>4:
[1, 2, 3, 4, 1]2<5: 不变。
结果：
[1, 2, 3, 4, 1]（满足了左边大的比右边多）
右 -> 左：
比较 5 和 2：
ratings[3](5) > ratings[4](2)。现有
candies[3] = 4。右边推导
candies[4] + 1 = 1 + 1 = 2。取 max(4, 2) = 4。
candies[3]还是 4。（说明为了满足左边给的4个，已经足够覆盖右边的需求了）。
比较 4 和 5：
ratings[2] < ratings[3]，不处理。...
最终：
[1, 2, 3, 4, 1]，和为 11。
再看个反例：[1, 2, 8, 5, 4](中间有个山峰)
左 -> 右：
[1, 2, 3, 1, 1](8比2大，给3个；5比8小，给1个)右 -> 左：
4: 1个
5: 比4大，
max(1, 1+1) = 2。数组变[..., 3, 2, 1]8: 比5大，
max(3, 2+1) = 3。数组变[..., 3, 2, 1]注意！这里 8 既比左边大，又比右边大，最后它拿了 3 个，依然保持了峰值地位。
复杂度分析
时间复杂度：O(N)
遍历了两次数组（正向一次，反向一次），求和一次。
3N依然是O(N)。
空间复杂度：O(N)
需要一个
candies数组来存储结果。
总结：Hard 题也不过如此
这道题之所以被标记为 Hard，是因为如果试图在一个循环里搞定左右两边，代码会变得极其复杂（需要回溯修改）。 但一旦使用了**“两次贪心，分别处理”**的策略，这道题就瞬间降维成了两道 Easy 题的叠加。
记住这个套路：当你发现一个元素需要同时满足左右两个邻居的约束时，试着先满足一边，再满足另一边。
下一题预告：根据身高重建队列
接下来这道题（LC 406），同样是关于**“两个维度”**的权衡。
每个人有两个属性：
h(身高),k(前面比我高的人数)。你需要给所有人重新排队，让每个人的
k属性都成立。
面对这种由(h, k)两个数字控制的乱序队列，我们应该先按身高排？还是先按人数排？ 贪心策略教我们：核心维度优先，次要维度插空。
下期见！