NC[130]. 分配糖果

🚩传送门：牛客题目
力扣题目

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 _1_ 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。
• 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

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

解题思路：左右遍历

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。

• 左规则：当 时， 号学生的糖果数量将比 号孩子的糖果数量多。
• 右规则：当 时， 号学生的糖果数量将比 号孩子的糖果数量多。

🚩先从左至右遍历学生成绩 **ratings**，按照以下规则给糖，并记录在 **left**中：

1. 将第一个孩子设置成 1 颗糖

   left[0]=1

2. 当 时， 号学生的糖果数量将比 号孩子的糖果数量多 1 个。

   left[i]=left[i-1]+1

3. 当 时， 号学生的糖果数量将设置成 1 个。

   left[i]=1

经过此规则分配后，可以保证所有学生糖数量 满足左规则 。

🚩再从右至左遍历学生成绩 **ratings**，按照以下规则给糖，并记录在 **right**中：

1. 将最后一个孩子设置成 Math.max(1,ans[n-1]) 颗糖

   right[n-1]=1

2. 当 时， 号学生的糖果数量将比 号孩子的糖果数量多 1 个。

   right[i]=right[i+1]+1

3. 当 时，号学生的糖果数量将设置成 1 个。

   right[i]=1

经过此规则分配后，可以保证所有学生糖数量 满足右规则 。

🚩 最后取 **left**和**right** 中每个下标的的最大值，求和返回即是最终的结果

节约数组可以优化成一个数组，因为我们只需要**left**和**right**中的最大值

复杂度分析

时间复杂度： ，其中 是数组 的长度。我们需要遍历两次数组

空间复杂度： ，其中 是数组 的长度。

我的代码

public class Solution {
    public int candy (int[] arr) {
        int n=arr.length;
        if(arr==null||n==0) return 0;
        int[]ans=new int[n];    // 分配辅助空间数组
        ans[0]=1;                // 第一个孩子给1个糖果
        // 从左向右,满足右规则
        for(int i=1;i<n;i++){
            if(arr[i]>arr[i-1])
                ans[i]=ans[i-1]+1;
            else
                ans[i]=1;
        }
        // 从右向左,满足左规则
        for(int i=n-2;i>=0;i--){
            if(arr[i]>arr[i+1])
                ans[i]=Math.max(ans[i+1]+1,ans[i]);    // 取ans[i+1]+1和ans[i]中的最大值
            else
                ans[i]=Math.max(1,ans[i]);            // 取1和ans[i]中的最大值
        }
        return Arrays.stream(ans).sum();            // 返回求和结果
    }
}