135.分发糖果

LeetCode LeetCode 数组 贪心
发布时间 :
字数:2.3k 阅读 : 评论:
  1. 135.分发糖果
    1. 135.1 题目
    2. 135.2 题解
      1. 左右双遍历
    3. 135.3 代码
    4. 135.4 运行结果

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.length
  • 1 <= n <= 2 * 10^4
  • 0 <= 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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏