分发糖果-CSDN博客

本文链接：https://blog.csdn.net/qq_37757277/article/details/145068063

分发糖果 ¹ 困难相关标签

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 * 104
0 <= ratings[i] <= 2 * 104

import java.util.Arrays;  

public class CandyDistribution {  
    public int candy(int[] ratings) {  
        // 获取孩子数量  
        int n = ratings.length;  
        // 初始化糖果数组，每位孩子至少分 1 颗糖果  
        int[] candies = new int[n];  
        Arrays.fill(candies, 1); // 初始化，每个孩子至少分 1 颗糖果  

        // 从左向右遍历，根据评分调整糖果数  
        for (int i = 1; i < n; i++) {  
            if (ratings[i] > ratings[i - 1]) {  
                // 如果当前孩子评分比左边孩子高，则比左边的糖果多一颗  
                candies[i] = candies[i - 1] + 1;  
            }  
        }  

        // 从右向左遍历，再次调整糖果数（确保右侧评分高的糖果数也正确）  
        for (int i = n - 2; i >= 0; i--) {  
            if (ratings[i] > ratings[i + 1]) {  
                // 如果当前孩子评分比右边孩子高，则取当前糖果数和右边孩子糖果 +1 的最大值  
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);  
            }  
        }  

        // 总糖果数  
        int totalCandies = 0;  
        for (int candy : candies) {  
            totalCandies += candy;  
        }  

        return totalCandies; // 返回最少糖果数  
    }  
    
    public static void main(String[] args) {  
        CandyDistribution solution = new CandyDistribution();  
        
        // 示例 1  
        int[] ratings1 = {1, 0, 2};  
        System.out.println(solution.candy(ratings1)); // 输出：5  
        
        // 示例 2  
        int[] ratings2 = {1, 2, 2};  
        System.out.println(solution.candy(ratings2)); // 输出：4  
    }  
}