难度: Hard
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
1 个糖果。请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
n == ratings.length1 <= n <= 2 * 1040 <= ratings[i] <= 2 * 104运行时间: 32 ms
内存: 18.2 MB
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n
# 从左到右遍历，保证相邻两个孩子中评分更高的孩子获得更多的糖果
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# 从右到左遍历，保证相邻两个孩子中评分更高的孩子获得更多的糖果，并且不破坏之前的分配
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
# 计算总共需要的糖果数目
return sum(candies)
该题解采用了两次遍历的方式来分配糖果。首先从左到右遍历，保证相邻两个孩子中评分更高的孩子获得更多的糖果。然后从右到左遍历，再次保证相邻两个孩子中评分更高的孩子获得更多的糖果，同时不破坏之前的分配。最后计算总共需要的糖果数目。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n # 初始化每个孩子分配到的糖果数为 1
# 从左到右遍历，保证相邻两个孩子中评分更高的孩子获得更多的糖果
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# 从右到左遍历，保证相邻两个孩子中评分更高的孩子获得更多的糖果，并且不破坏之前的分配
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
# 计算总共需要的糖果数目
return sum(candies)
单次遍历无法确保同时满足左右两边孩子之间评分与糖果数的关系。例如，从左到右遍历时，我们确保每个孩子与其左边的孩子评分较高时获得更多糖果。但这种方式可能忽略了右边孩子的评分情况，导致评分高的孩子糖果数不足。因此，需要从右到左再进行一次遍历，以保证右边的孩子如果评分更高也能获得更多糖果。两次遍历确保了无论是左边还是右边的孩子，只要评分更高，就能获得更多糖果。
第二次遍历使用`max`函数是为了确保在满足从右到左的孩子评分更高获得更多糖果的同时，不破坏第一次遍历对左边孩子评分更高时的糖果分配。`max`函数确保如果第一次遍历给出的糖果数已经足够，就保持不变；如果不足，则进行更新，以适应右边邻居的评分。这样，我们既保持了第一次遍历的结果，也满足了新的条件。
初始化所有孩子的糖果数为1是基于至少每个孩子需要获得一颗糖果的最基本需求。这是问题的基本条件，保证每个孩子至少有糖果。这种初始化本身不会导致不公平，因为之后的两次遍历过程会根据孩子之间的评分差异调整糖果数，以确保评分较高的孩子获得更多糖果。
对于单调递增或递减的`ratings`数组，这种双遍历方法仍然有效，但效率不是最优的。例如，在单调递增的数组中，一次从左到右的遍历就足以解决问题，因为每个后续的孩子评分都比前一个高，只需逐个增加糖果数即可；同理，单调递减的数组只需一次从右到左的遍历。尽管这样，使用双遍历方法在任何情况下都是安全的，保证了解决方案的正确性，但在已知数组单调性的情况下，可以采用单次遍历以提升效率。