LC135. 分发糖果

题目描述

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

题目解析

题目在说什么

想象你是一个老师，要给一排小朋友发糖果。每个小朋友都有一个“评分”（ratings数组里的数字）。发糖果有两个规则：

1. 每个小朋友至少拿到1颗糖——不能有人没糖吃。 2. 相邻的两个小朋友，评分高的那个必须拿到更多糖——比如左边小朋友评分3，右边评分5，那么右边小朋友的糖必须比左边多。

问题是：在满足这两个规则的前提下，最少需要准备多少颗糖？

注意：规则只要求“相邻比较”，不要求跨过中间的人比较。比如第一个和第三个评分高低不影响，只看相邻的两个人。

---

思路是怎么来的

第一步：先满足“每人至少1颗”

最简单的方法：先给每个小朋友发1颗糖。这样规则1就满足了。但规则2还没处理。

第二步：处理“左边比右边高”的情况

我们想象一个场景：从左到右看，如果发现某个小朋友的评分比左边的高，那他的糖必须比左边多。比如左边有2颗，那这个小朋友至少要有3颗。

这就像排队时，你看到前面的人比你矮，但评分比你低，你就得比他多一颗糖。我们只需要从左到右扫一遍，遇到“右边评分高”的情况，就把右边孩子的糖数改成“左边糖数+1”。

第三步：处理“右边比左边高”的情况

但只从左到右看还不够。比如评分是 [1, 2, 1]，从左到右处理后，第二个孩子糖数变成2（比第一个多1），第三个孩子还是1。但第三个孩子评分是1，比第二个的2低，所以第三个不需要比第二个多，没问题。但如果评分是 [2, 1, 2] 呢？从左到右：第一个1颗，第二个评分比第一个低，所以还是1颗，第三个评分比第二个高，所以第三个变成2颗。但这时第一个评分2比第二个1高，却只得到1颗糖，违反了规则2（因为第一个和第二个相邻，第一个评分更高，应该比第二个多）。所以我们需要再从右到左检查一遍。

从右到左看，如果发现某个小朋友的评分比右边的高，那他的糖必须比右边多。比如右边有2颗，那这个小朋友至少要有3颗。同时，这个小朋友可能已经在第一轮（从左到右）时被调整过，比如已经拿到了3颗，那就不需要再改；但如果第一轮只给了1颗，而右边有2颗，那就要改成3颗。所以我们要取“第一轮的结果”和“右边糖数+1”中的最大值，这样就能同时满足两个方向的要求。

为什么两次遍历就够了？

因为规则只涉及相邻比较，所以只要保证每个孩子：

• 比左边评分高时，糖数比左边多（左到右检查）
• 比右边评分高时，糖数比右边多（右到左检查）

这两个条件同时满足，就相当于所有相邻关系都处理好了。而两次遍历正好分别处理这两个方向。

---

代码逐步拆解

我们来看参考代码，一行一行解释。

int[] candys = new int[ratings.length];
Arrays.fill(candys, 1);

• 创建一个数组 candys，长度和孩子数量一样，用来存每个孩子的糖数。
• 先用 Arrays.fill 把所有位置填成1，满足“每人至少1颗”。

for(int i = 1; i < ratings.length; i++){
    if(ratings[i] > ratings[i - 1]){
        candys[i] = candys[i - 1] + 1;
    } 
}

• 从左到右遍历，从第二个孩子（索引1）开始。
• 如果当前孩子的评分比左边高，就把他的糖数改成左边糖数+1。
• 注意：这里只处理“右边比左边高”的情况，不处理“左边比右边高”（因为左边已经在之前的循环中处理过了）。

例子：ratings = [1, 0, 2]

• 初始 candys = [1, 1, 1]
• i=1: 评分0 < 1，不触发
• i=2: 评分2 > 0，触发，candys[2] = candys[1] + 1 = 2
• 结果 candys = [1, 1, 2]

int result = candys[ratings.length - 1];

• 先记录最后一个孩子的糖数，因为后面从右到左遍历时，我们会从倒数第二个开始累加，最后再加最后一个。

for(int i = ratings.length - 2; i >= 0; i--) {
    if(ratings[i] > ratings[i + 1]){
        candys[i] = Math.max(candys[i + 1] + 1, candys[i]);
    } 
    result += candys[i];
}