Leetcode 每日一题 135.分发糖果

问题描述

给定一个整数数组 ratings，表示一排孩子的评分。我们需要按照以下规则给孩子们分发糖果：

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

我们的目标是计算出按照这些规则分发糖果所需的最少糖果数。

输入输出格式

• 输入：一个整数数组 ratings。
• 输出：一个整数，表示最少需要准备的糖果数。

示例

1. 输入：ratings = [1,0,2] 输出：5 解释：给第一个、第二个、第三个孩子分别分发2、1、2颗糖果。

2. 输入：ratings = [1,2,2] 输出：4 解释：给第一个、第二个、第三个孩子分别分发1、2、1颗糖果。

难点分析

这个问题的难点在于如何高效地分配糖果，同时满足每个孩子至少得到1个糖果，以及评分高的孩子得到更多糖果的条件。

算法选择

我们选择使用贪心算法来解决这个问题。贪心算法在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。

算法逻辑

1. 初始化：为每个孩子分配1个糖果，用数组 arr 表示，长度与 ratings 相同，初始值都为1。

2. 从左到右遍历：遍历 ratings 数组，如果当前孩子的评分低于下一个孩子的评分（即 ratings[i] < ratings[i+1]），则下一个孩子的糖果数至少为当前孩子的糖果数加1（即 arr[i+1] = arr[i] + 1）。

3. 从右到左遍历：反向遍历 ratings 数组，如果当前孩子的评分高于前一个孩子的评分，并且前一个孩子的糖果数不小于当前孩子的糖果数（即 ratings[i] > ratings[i-1] && arr[i-1] <= arr[i]），则前一个孩子的糖果数更新为当前孩子的糖果数加1（即 arr[i-1] = arr[i] + 1）。

4. 计算总糖果数：遍历 arr 数组，将所有孩子的糖果数相加，得到总糖果数。

代码实现

以下是使用Java语言实现的代码：

java

class Solution {
    public int candy(int[] ratings) {
        int[] arr = new int[ratings.length];
        for(int i=0;i<arr.length;i++){
            arr[i]=1;
        }
        for(int i=0;i<arr.length-1;i++){
            if(ratings[i]<ratings[i+1]){
                arr[i+1]=arr[i]+1;
            }
        }
        for(int i =arr.length-1;i>0;i--){
            if(ratings[i]<ratings[i-1]&&arr[i-1]<=arr[i]){
                arr[i-1]=arr[i]+1;
            }
        }
        int sum=0;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
        }
        return sum;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中n是 ratings 数组的长度。我们对数组进行了两次遍历。
• 空间复杂度：O(n)，用于存储每个孩子分配的糖果数。