前言：LeetCode 135. 分发糖果是数组贪心算法的经典应用题，核心考察“双向贪心”的解题思维，也是面试中高频出现的中等难度题目。本文将从题干解析、解题思路、代码实现、复杂度分析、边界案例拓展五个维度，全方位拆解该题的解决过程，兼顾新手理解与进阶提升，助力大家吃透贪心思想在数组问题中的应用。
关键词：LeetCode 135；分发糖果；贪心算法；数组；双向遍历；算法解析
一、题干深度解析
1.1 题目要求
有 n 个孩子站成一排，给定整数数组 ratings 表示每个孩子的评分，按以下两个规则分发糖果，计算需要准备的最少糖果数目：
每个孩子至少分配到 1 个糖果（基础条件，确保无孩子分不到糖果）；
相邻两个孩子中，评分更高的那个会获得更多的糖果（核心约束，需兼顾左右相邻两个方向）。
1.2 示例拆解
通过两个示例，快速理解规则的应用的核心，避免踩坑：
示例 1：输入 ratings = [1,0,2]
输出：5；分发方案：[2,1,2]
解析：
孩子1（评分1） vs 孩子2（评分0）：孩子1评分高，需比孩子2多，孩子2至少1颗 → 孩子1至少2颗；
孩子2（评分0） vs 孩子3（评分2）：孩子3评分高，需比孩子2多 → 孩子3至少2颗；
总和：2+1+2=5，满足“最少糖果”要求。
示例 2：输入 ratings = [1,2,2]
输出：4；分发方案：[1,2,1]
解析：
孩子1（1） vs 孩子2（2）：孩子2评分高 → 孩子2至少2颗，孩子1至少1颗；
孩子2（2） vs 孩子3（2）：评分相等，无“更多糖果”要求 → 孩子3至少1颗即可；
总和：1+2+1=4，符合规则且糖果数最少（若孩子3分2颗，总和为5，不符合“最少”）。
1.3 核心难点
本题的关键陷阱的是“单向遍历无法满足约束”：仅从左到右遍历，会忽略“右侧孩子评分高于左侧”的情况；仅从右到左遍历，会忽略“左侧孩子评分高于右侧”的情况。因此，必须采用“双向贪心”，兼顾两个方向的约束。
二、解题思路（双向贪心，最优解法）
核心思想：贪心算法的核心是“局部最优→全局最优”，本题中“局部最优”是“每个孩子在自己的相邻关系中，满足评分高则糖果多”，通过两次遍历（左→右、右→左），逐步实现全局最优。
具体步骤：
步骤1：初始化糖果数组
创建一个与 ratings 长度相同的糖果数组 candies，初始值均为 1，满足“每个孩子至少1颗糖果”的基础条件。
步骤2：左→右遍历，处理“左侧评分低于右侧”的情况
从索引 1 开始（跳过第一个孩子），遍历至数组末尾：
若 ratings[i] > ratings[i-1]，说明当前孩子评分高于左侧相邻孩子，此时 candies[i] = candies[i-1] + 1（确保当前孩子糖果数比左侧多，满足局部最优）。
此时，数组已满足“所有左侧评分低于右侧的孩子，糖果数更多”，但未处理“右侧评分低于左侧”的情况。
步骤3：右→左遍历，处理“右侧评分低于左侧”的情况
从索引 len(ratings)-2 开始（跳过最后一个孩子），遍历至数组开头：
若 ratings[i] > ratings[i+1]，说明当前孩子评分高于右侧相邻孩子，此时需比较 candies[i] 与 candies[i+1] + 1：
若 candies[i] 已大于 candies[i+1] + 1，说明左→右遍历时已满足“当前孩子糖果数比右侧多”，无需修改；
若 candies[i] ≤ candies[i+1] + 1，说明左→右遍历未覆盖该情况，需更新 candies[i] = candies[i+1] + 1（确保当前孩子糖果数比右侧多）。
步骤4：计算糖果总数
遍历 candies 数组，求和即为需要准备的最少糖果数目。
思路验证（结合示例1）
ratings = [1,0,2]
初始化 candies = [1,1,1]；
左→右遍历：
i=1：ratings[1]=0 < ratings[0]=1 → 不修改，candies=[1,1,1]；
i=2：ratings[2]=2 > ratings[1]=0 → candies[2] = 1+1=2 → candies=[1,1,2]；
- 右→左遍历：
i=1：ratings[1]=0 < ratings[2]=2 → 不修改；
i=0：ratings[0]=1 > ratings[1]=0 → candies[0] = 1+1=2 → candies=[2,1,2]；
- 求和：2+1+2=5，与示例输出一致。
三、完整代码实现（Python）
严格按照题干要求的类与方法格式编写，添加详细注释，确保可直接复制运行，适配LeetCode提交规范：
classSolution:defcandy(self,ratings:List[int])->int:""" 分发糖果：满足两个条件，计算最少需要的糖果数目 :param ratings: 每个孩子的评分数组 :return: 最少糖果数目 """n=len(ratings)# 步骤1：初始化糖果数组，每个孩子至少1颗糖果candies=[1]*n# 步骤2：左→右遍历，处理左侧评分低于右侧的情况foriinrange(1,n):# 若当前孩子评分高于左侧，糖果数比左侧多1ifratings[i]>ratings[i-1]:candies[i]=candies[i-1]+1# 步骤3：右→左遍历，处理右侧评分低于左侧的情况foriinrange(n-2,-1,-1):# 若当前孩子评分高于右侧，确保糖果数比右侧多（取较大值，避免覆盖左→右的结果）ifratings[i]>ratings[i+1]:candies[i]=max(candies[i],candies[i+1]+1)# 步骤4：返回糖果总数returnsum(candies)四、代码解析与复杂度分析
4.1 代码细节解析
初始化：candies = [1] * n，直接满足“每个孩子至少1颗糖果”，时间复杂度O(n)；
左→右遍历：range(1, n)，遍历n-1次，每次仅做一次判断和赋值，时间复杂度O(n)；
右→左遍历：range(n-2, -1, -1)，同样遍历n-1次，核心是“取max”，避免覆盖左→右遍历的有效结果（比如左侧孩子已通过左→右遍历获得更多糖果，无需再修改）；
求和：sum(candies)，时间复杂度O(n)。
4.2 复杂度分析
时间复杂度：O(n)，总共进行3次线性遍历（初始化、左→右、右→左），无嵌套循环，效率最优；
空间复杂度：O(n)，需要额外创建一个长度为n的candies数组，用于存储每个孩子的糖果数。
补充：本题可实现O(1)空间复杂度（无需额外数组），但逻辑更复杂，新手不推荐，面试中若能写出O(n)空间的最优解，已满足要求。
五、边界案例与易错点拓展
刷题时，边界案例往往是出错的重灾区，以下梳理4类核心边界案例，结合代码验证，帮助大家规避易错点。
5.1 边界案例1：n=1（只有一个孩子）
输入：ratings = [5] → 输出：1（仅需1颗糖果，满足基础条件）；
代码验证：candies = [1]，sum=1，正确。
5.2 边界案例2：评分严格递增
输入：ratings = [1,2,3,4,5] → 输出：1+2+3+4+5=15；
代码验证：左→右遍历后 candies = [1,2,3,4,5]，右→左遍历无修改，求和15，正确。
5.3 边界案例3：评分严格递减
输入：ratings = [5,4,3,2,1] → 输出：5+4+3+2+1=15；
代码验证：左→右遍历无修改（均为1），右→左遍历后 candies = [5,4,3,2,1]，求和15，正确。
5.4 边界案例4：评分波动（易错点）
输入：ratings = [1,3,2,1] → 输出：1+2+1+1=5；
解析：左→右遍历后 candies = [1,2,1,1]；右→左遍历i=2（ratings[2]=2 > ratings[3]=1，candies[2] = max(1, 1+1)=2），最终 candies = [1,2,2,1]，求和6？
注意：此处易错！正确输出应为6，原思路中右→左遍历i=2时，ratings[2]=2 > ratings[3]=1，需更新 candies[2] = 2，最终总和1+2+2+1=6，代码可正确处理，避免“漏更”问题。
5.5 核心易错点总结
忘记“双向遍历”，仅做单向遍历，导致一侧约束不满足；
右→左遍历时，未取max，直接赋值 candies[i] = candies[i+1]+1，覆盖左→右遍历的有效结果；
初始化糖果数组时，未给每个孩子赋1颗，导致基础条件不满足。
六、总结与进阶思考
6.1 解题总结
LeetCode 135. 分发糖果的核心是“双向贪心”，通过两次线性遍历，分别处理左右两个方向的相邻约束，最终实现全局最优。该题的关键是理解“单向遍历无法覆盖所有场景”，以及“取max避免结果覆盖”的细节，代码逻辑简洁，效率最优，是贪心算法在数组问题中的典型应用。
6.2 进阶思考
如何实现O(1)空间复杂度？（提示：用两个变量记录当前糖果数和前一个孩子的糖果数，替代数组）；
若题目新增“相邻孩子评分相等时，糖果数必须相等”，该如何修改代码？（提示：调整遍历条件，相等时赋值为相同糖果数）。
结语：本题是贪心算法的入门必刷题，掌握双向遍历的思路后，可迁移到类似的“相邻约束”数组问题中（如LeetCode 455. 分发饼干）。建议大家动手复现代码，测试所有边界案例，真正吃透贪心思想的“局部最优→全局最优”逻辑。
