前言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颗总和2125满足“最少糖果”要求。示例 2输入 ratings [1,2,2]输出4分发方案[1,2,1]解析孩子11 vs 孩子22孩子2评分高 → 孩子2至少2颗孩子1至少1颗孩子22 vs 孩子32评分相等无“更多糖果”要求 → 孩子3至少1颗即可总和1214符合规则且糖果数最少若孩子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[i1]说明当前孩子评分高于右侧相邻孩子此时需比较 candies[i] 与 candies[i1] 1若 candies[i] 已大于 candies[i1] 1说明左→右遍历时已满足“当前孩子糖果数比右侧多”无需修改若 candies[i] ≤ candies[i1] 1说明左→右遍历未覆盖该情况需更新 candies[i] candies[i1] 1确保当前孩子糖果数比右侧多。步骤4计算糖果总数遍历 candies 数组求和即为需要准备的最少糖果数目。思路验证结合示例1ratings [1,0,2]初始化 candies [1,1,1]左→右遍历i1ratings[1]0 ratings[0]1 → 不修改candies[1,1,1]i2ratings[2]2 ratings[1]0 → candies[2] 112 → candies[1,1,2]右→左遍历i1ratings[1]0 ratings[2]2 → 不修改i0ratings[0]1 ratings[1]0 → candies[0] 112 → candies[2,1,2]求和2125与示例输出一致。三、完整代码实现Python严格按照题干要求的类与方法格式编写添加详细注释确保可直接复制运行适配LeetCode提交规范classSolution:defcandy(self,ratings:List[int])-int: 分发糖果满足两个条件计算最少需要的糖果数目 :param ratings: 每个孩子的评分数组 :return: 最少糖果数目 nlen(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[i1]:candies[i]max(candies[i],candies[i1]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 边界案例1n1只有一个孩子输入ratings [5] → 输出1仅需1颗糖果满足基础条件代码验证candies [1]sum1正确。5.2 边界案例2评分严格递增输入ratings [1,2,3,4,5] → 输出1234515代码验证左→右遍历后 candies [1,2,3,4,5]右→左遍历无修改求和15正确。5.3 边界案例3评分严格递减输入ratings [5,4,3,2,1] → 输出5432115代码验证左→右遍历无修改均为1右→左遍历后 candies [5,4,3,2,1]求和15正确。5.4 边界案例4评分波动易错点输入ratings [1,3,2,1] → 输出12115解析左→右遍历后 candies [1,2,1,1]右→左遍历i2ratings[2]2 ratings[3]1candies[2] max(1, 11)2最终 candies [1,2,2,1]求和6注意此处易错正确输出应为6原思路中右→左遍历i2时ratings[2]2 ratings[3]1需更新 candies[2] 2最终总和12216代码可正确处理避免“漏更”问题。5.5 核心易错点总结忘记“双向遍历”仅做单向遍历导致一侧约束不满足右→左遍历时未取max直接赋值 candies[i] candies[i1]1覆盖左→右遍历的有效结果初始化糖果数组时未给每个孩子赋1颗导致基础条件不满足。六、总结与进阶思考6.1 解题总结LeetCode 135. 分发糖果的核心是“双向贪心”通过两次线性遍历分别处理左右两个方向的相邻约束最终实现全局最优。该题的关键是理解“单向遍历无法覆盖所有场景”以及“取max避免结果覆盖”的细节代码逻辑简洁效率最优是贪心算法在数组问题中的典型应用。6.2 进阶思考如何实现O(1)空间复杂度提示用两个变量记录当前糖果数和前一个孩子的糖果数替代数组若题目新增“相邻孩子评分相等时糖果数必须相等”该如何修改代码提示调整遍历条件相等时赋值为相同糖果数。结语本题是贪心算法的入门必刷题掌握双向遍历的思路后可迁移到类似的“相邻约束”数组问题中如LeetCode 455. 分发饼干。建议大家动手复现代码测试所有边界案例真正吃透贪心思想的“局部最优→全局最优”逻辑。