华为 OD 训练营 · 题解精讲
LC135. 分发糖果
LC135. 分发糖果 视频地址：https://uha.xet.tech/s/ifcWl
题目描述
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求，给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。 示例 1： 输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。 示例 2： 输入：ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。 提示： n == ratings.length 1 <= n <= 2 * 10^4 0 <= ratings[i] <= 2 * 10^4
题目解析
解题思路
本题要求相邻评分更高的孩子获得更多糖果，且总糖果数最少。核心思想是将规则拆分为两个方向分别处理，再合并结果。
- 左规则：从左向右遍历，若当前孩子评分高于左边，则糖果数至少比左边多1。
- 右规则：从右向左遍历，若当前孩子评分高于右边，则糖果数至少比右边多1。
最终每个孩子的糖果数需同时满足两个规则，因此取两次计算结果的最大值。
数据结构：一维数组 candys 存储每个孩子糖果数，初始全为1。
关键步骤
1. 初始化：所有孩子先分1颗糖，保证最低要求。 2. 左遍历：i 从1到n-1，若 ratings[i] > ratings[i-1]，则 candys[i] = candys[i-1] + 1。 3. 右遍历并累加：i 从n-2到0，若 ratings[i] > ratings[i+1]，则 candys[i] = max(candys[i], candys[i+1] + 1)。同时累加结果，从最右孩子开始。
示例 ratings = [1,0,2]
左遍历后 candys = [1,1,2] （因为 0<2 触发更新）
右遍历：i=1时 0<1? 否，不变；i=0时 1>0? 是，candys[0]=max(1, candys[1]+1=2)=2
最终 candys = [2,1,2]，总和5复杂度分析
- 时间复杂度：O(n)，两次线性遍历，n为数组长度。
- 空间复杂度：O(n)，用于存储糖果数组。
参考代码
class Solution:
def candy(self, ratings: List[int]) -> int:
# 存储每个孩子的糖果
# 先给所有孩子 1 颗糖
candys = [1 for _ in range(len(ratings))]
# 从左至右遍历数组 ratings
for i in range( 1 , len(ratings)) :
# 如果发现当前孩子的评分比【左边】的更高
if ratings[i] > ratings[i - 1] :
# 那么当前孩子的糖果数量需要比【左边】孩子的糖果数量多 1 个
candys[i] = candys[i - 1] + 1
# 记录糖果数量，初始为最右边的值
result = candys[-1]
# 从右至左遍历数组 ratings
for i in range( len(ratings) - 2 , -1 , - 1 ) :
# 如果发现当前孩子的评分比【右边】的更高
if ratings[i] > ratings[i + 1] :
# 那么当前孩子的糖果数量需要比【右边】孩子的糖果数量多 1 个
# 当前孩子在第一轮循环中已经设置了值
# 所以取这两个值的最大值
# 这样同时满足左规则和右规则
candys[i] = max( candys[i + 1] + 1 , candys[i])
# candys[i] 已经是符合左规则和右规则的值了
# 累加到 result 上面
result += candys[i]
# 返回结果
return result