135.分发糖果
135.1 题目
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 * 10^40 <= ratings[i] <= 2 * 10^4
135.2 题解
左右双遍历
// 方法一：左右双遍历
// 根据题意描述中：相邻两个孩子评分更高的孩子会获得更多的糖果
// 我们可以得到以下信息：
// 假设左右相邻的学生 a 和 b，a 在 b 左边;
// 当 ratings[a] < ratings[b] 时，b 的糖要比 a 分得多
// 当 ratings[a] > ratings[b] 时，a 的糖要比 b 分得多
// 那么我们完全可以通过两次遍历，来达到目的。
// 我们需要使用两个数组来记录左右遍历后分配的糖果数
// 第 1 次遍历：
// 从左到右遍历学生的成绩ratings，按以下规则给糖，并将结果记录到 left 数组中
// 1. 第一个学生默认给一颗糖
// 2. 除第一个学生外，ratings[i] > ratings[i - 1]，则第 i 个学生糖要比 第 i - 1 个学生多 1 颗
// 3. 若 ratings[i] <= ratings[i - 1]，则默认给第 i 个学生 1 颗糖，因为学生至少得有糖
// 经过这一步后，可以保证所有学生满足：当 ratings[a] < ratings[b] 时，b 的糖要比 a 分得多
// 第2次遍历：
// 从右到左遍历学生的成绩ratings，按以下规则给糖，并将结果记录到right数组中
// 1. 第一个学生默认给一颗糖
// 2. 除第一个学生外，ratings[i] > ratings[i + 1]，则第 i 个学生糖要比 第 i + 1 个学生多 1 颗
// 3. 若 ratings[i] <= ratings[i + 1]，则默认给第 i 个学生 1 颗糖，因为学生至少得有糖
// 经过这一步后，可以保证所有学生满足：当 ratings[a] > ratings[b] 时，a 的糖要比 b 分得多
// 两次遍历后，我们需要取左右数组中较大的值作为最终分配结果
// 最终，我们从2次遍历分配糖果的结果数组 left 和 right 当中记录对应学生糖果数量的最大值，这样就能满足：相邻两个孩子评分更高的孩子会获得更多的糖果
// 取两个数组的最大值 保证了每个孩子至少分配一个糖果
static int Candy1(int[] ratings)
{
int result = 0; // 初始化结果为0
int[] leftArray = new int[ratings.Length]; // 创建一个数组存储从左往右遍历时每个孩子分配的糖果数
int[] rightArray = new int[ratings.Length]; // 创建一个数组存储从右往左遍历时每个孩子分配的糖果数
for (int i = 0; i < ratings.Length; i++) // 从左往右遍历评分数组
{
if (i > 0 && ratings[i] > ratings[i - 1]) // 如果当前孩子评分高于前一个孩子
{
leftArray[i] = leftArray[i - 1] + 1; // 当前孩子糖果数等于前一个孩子糖果数加一
}
else
{
leftArray[i] = 1; // 否则当前孩子分配一个糖果
}
}
for (int i = ratings.Length - 1; i >= 0; i--) // 从右往左遍历评分数组
{
if (i < ratings.Length - 1 && ratings[i] > ratings[i + 1]) // 如果当前孩子评分高于后一个孩子
{
rightArray[i] = rightArray[i + 1] + 1; // 当前孩子糖果数等于后一个孩子糖果数加一
}
else
{
rightArray[i] = 1; // 否则当前孩子分配一个糖果
}
}
for (int i = 0; i < ratings.Length; i++) // 遍历孩子数组
{
result += Math.Max(leftArray[i], rightArray[i]); // 结果加上左右两边糖果数的最大值
}
return result; // 返回结果
}
135.3 代码
using System;
class Program
{
static void Main()
{
#region 题目
// n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
// 你需要按照以下要求，给这些孩子分发糖果：
// 1. 每个孩子至少分配到 1 个糖果。
// 2. 相邻两个孩子评分更高的孩子会获得更多的糖果。
// 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目。
// 示例 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 * 104
// 0 <= ratings[i] <= 2 * 104
#endregion
#region 测试
// 示例 1
int[] ratings1 = { 1, 0, 2 };
int result1_1 = Candy1(ratings1);
Console.WriteLine($"示例1 方法1 输出：{result1_1}");
// 示例 2
int[] ratings2 = { 1, 2, 2 };
int result2_1 = Candy1(ratings2);
Console.WriteLine($"示例2 方法1 输出：{result2_1}");
#endregion
}
#region 答案
// 方法一：左右双遍历
// 根据题意描述中：相邻两个孩子评分更高的孩子会获得更多的糖果
// 我们可以得到以下信息：
// 假设左右相邻的学生 a 和 b，a 在 b 左边;
// 当 ratings[a] < ratings[b] 时，b 的糖要比 a 分得多
// 当 ratings[a] > ratings[b] 时，a 的糖要比 b 分得多
// 那么我们完全可以通过两次遍历，来达到目的。
// 我们需要使用两个数组来记录左右遍历后分配的糖果数
// 第 1 次遍历：
// 从左到右遍历学生的成绩ratings，按以下规则给糖，并将结果记录到 left 数组中
// 1. 第一个学生默认给一颗糖
// 2. 除第一个学生外，ratings[i] > ratings[i - 1]，则第 i 个学生糖要比 第 i - 1 个学生多 1 颗
// 3. 若 ratings[i] <= ratings[i - 1]，则默认给第 i 个学生 1 颗糖，因为学生至少得有糖
// 经过这一步后，可以保证所有学生满足：当 ratings[a] < ratings[b] 时，b 的糖要比 a 分得多
// 第2次遍历：
// 从右到左遍历学生的成绩ratings，按以下规则给糖，并将结果记录到right数组中
// 1. 第一个学生默认给一颗糖
// 2. 除第一个学生外，ratings[i] > ratings[i + 1]，则第 i 个学生糖要比 第 i + 1 个学生多 1 颗
// 3. 若 ratings[i] <= ratings[i + 1]，则默认给第 i 个学生 1 颗糖，因为学生至少得有糖
// 经过这一步后，可以保证所有学生满足：当 ratings[a] > ratings[b] 时，a 的糖要比 b 分得多
// 两次遍历后，我们需要取左右数组中较大的值作为最终分配结果
// 最终，我们从2次遍历分配糖果的结果数组 left 和 right 当中记录对应学生糖果数量的最大值，这样就能满足：相邻两个孩子评分更高的孩子会获得更多的糖果
// 取两个数组的最大值 保证了每个孩子至少分配一个糖果
static int Candy1(int[] ratings)
{
int result = 0; // 初始化结果为0
int[] leftArray = new int[ratings.Length]; // 创建一个数组存储从左往右遍历时每个孩子分配的糖果数
int[] rightArray = new int[ratings.Length]; // 创建一个数组存储从右往左遍历时每个孩子分配的糖果数
for (int i = 0; i < ratings.Length; i++) // 从左往右遍历评分数组
{
if (i > 0 && ratings[i] > ratings[i - 1]) // 如果当前孩子评分高于前一个孩子
{
leftArray[i] = leftArray[i - 1] + 1; // 当前孩子糖果数等于前一个孩子糖果数加一
}
else
{
leftArray[i] = 1; // 否则当前孩子分配一个糖果
}
}
for (int i = ratings.Length - 1; i >= 0; i--) // 从右往左遍历评分数组
{
if (i < ratings.Length - 1 && ratings[i] > ratings[i + 1]) // 如果当前孩子评分高于后一个孩子
{
rightArray[i] = rightArray[i + 1] + 1; // 当前孩子糖果数等于后一个孩子糖果数加一
}
else
{
rightArray[i] = 1; // 否则当前孩子分配一个糖果
}
}
for (int i = 0; i < ratings.Length; i++) // 遍历孩子数组
{
result += Math.Max(leftArray[i], rightArray[i]); // 结果加上左右两边糖果数的最大值
}
return result; // 返回结果
}
#endregion
}
135.4 运行结果
示例1 方法1 输出：5
示例2 方法1 输出：4
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
