135. 分发糖果

分发糖果问题

题目描述

给定一个整数数组 ratings，表示 n 个孩子的评分。需要按照以下要求分发糖果：

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

计算并返回需要准备的最少糖果数目。

示例 1:

输入: ratings = [1,0,2]
输出: 5
解释: 你可以给第一个、第二个和第三个孩子分别分发 2、1、2 块糖果。

示例 2:

输入: ratings = [1,2,2]
输出: 4
解释: 你可以给第一个、第二个和第三个孩子分别分发 1、2、1 块糖果。
      第一个孩子只需要 1 块糖果，因为他的评分比第二个孩子低。
      第二个和第三个孩子必须分别获得 2 块糖果，他们有相同的评分。

题解

这个问题可以通过贪心算法解决。我们需要从两端向中间遍历数组，对于每个孩子，我们根据其评分与相邻孩子评分的高低来确定其糖果数。由于评分更高的孩子需要更多的糖果，我们可以从两端开始，以确保中间的孩子不会因为两端的孩子评分更高而需要更多的糖果。

下面是使用 Go 语言实现的代码：

package main

import (
	"fmt"
	"math"
)

func minCandies(ratings []int) int {
	n := len(ratings)
	candies := make([]int, n)
	totalCandies := 0

	// 从左到右遍历
	for i := 0; i < n; i++ {
		candies[i] = 1
		if i > 0 && ratings[i] > ratings[i-1] {
			candies[i] = candies[i-1] + 1
		}
		totalCandies += candies[i]
	}

	// 从右到左遍历
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] && candies[i] <= candies[i+1] {
			candies[i] = candies[i+1] + 1
			totalCandies += candies[i] - 1 // 因为之前计算过一遍
		}
	}

	return totalCandies
}

func main() {
	fmt.Println(minCandies([]int{1, 0, 2})) // 输出: 5
	fmt.Println(minCandies([]int{1, 2, 2})) // 输出: 4
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 ratings 的长度。我们只需要遍历两次数组即可。
• 空间复杂度：O(n)，我们需要一个与原数组相同大小的数组来存储每个孩子分到的糖果数。