题目描述#

有 n 个孩子站成一排，ratings[i] 表示第 i 个孩子的评分。

需要给每个孩子分发糖果，满足：

1. 每个孩子至少分到 1 个糖果。
2. 相邻孩子中评分更高的孩子必须获得更多糖果。

请计算满足条件时需要的 最少糖果数。

知识边界#

贪心思想#

题目本质是 相邻关系约束的最小分配问题。

如果评分连续上升：

1 2 3 4

糖果必须为：

1 2 3 4

如果连续下降：

4 3 2 1

糖果必须为：

4 3 2 1

因此评分数组可以拆成 山峰结构：

上升段 + 下降段

设：

• up：上升长度
• down：下降长度

额外糖果为：

max(up, down) + (up-1)*up/2 + (down-1)*down/2

其中 (k-1)*k/2 是等差数列求和。

Go 实现注意点#

1. ans := n

因为每个孩子至少一个糖果。

2. 在 for 循环内部移动 i

for i+1 < n && ratings[i] < ratings[i+1] {
	i++
}

这种写法用于 扫描连续区间。

思路#

遍历数组，将评分划分为若干 山峰结构。

步骤：

1. 记录起点 start
2. 向右找到 严格上升段，得到山顶 top
3. 继续找到 严格下降段
4. 计算：

up = top - start
down = i - top

5. 将这一段的最小糖果数加入答案。

时间复杂度#

O(n)

每个位置最多被扫描一次。

空间复杂度#

O(1)

只使用常数变量。

代码#

func candy(ratings []int) int {
	n := len(ratings)
	ans := n
	for i := 0; i < n; i++ {
		start := i
		if i > 0 && ratings[i-1] < ratings[i] {
			start--
		}
		// 找绝对攀升
		for i+1 < n && ratings[i] < ratings[i+1] {
			i++
		} // 当前 i 为顶峰
		top := i
		// 找绝对下降
		for i+1 < n && ratings[i] > ratings[i+1] {
			i++
		} // 当前为最低点
		up := top - start
		down := i - top
		ans += max(up, down) + (up-1)*up/2 + (down-1)*down/2
	}
	return ans
}