JAVA学习-练习试用Java实现“分发糖果”

问题：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。

评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1：

输入：[1,0,2]

输出：5

解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：[1,2,2]

输出：4

解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

解答思路：

以下是使用 Java 语言解决此问题的代码：

import java.util.ArrayList;

import java.util.List;



public class CandyDistribution {

    public static void main(String[] args) {

        int[] ratings = {1, 0, 2};

        System.out.println(distributeCandies(ratings));

    }



    public static int distributeCandies(int[] ratings) {

        List<Integer> candies = new ArrayList<>();



        for (int i = 0; i < ratings.length; i++) {

            candies.add(1);

        }



        for (int i = 1; i < ratings.length; i++) {

            if (ratings[i] > ratings[i - 1]) {

                candies.set(i, candies.get(i - 1) + 1);

            } else if (ratings[i] < ratings[i - 1]) {

                int j = i;



                while (j > 0 && ratings[j] < ratings[j - 1] && candies.get(j) >= candies.get(j - 1)) {

                    candies.set(j - 1, candies.get(j) + 1);

                    j--;

                }

            }

        }



        int sum = 0;



        for (Integer candy : candies) {

            sum += candy;

        }



        return sum;

    }

}

这段代码首先初始化一个包含每个孩子 1 颗糖果的列表。然后，它遍历评分数组。如果当前孩子的评分高于前一个孩子的评分，它会将当前孩子的糖果数增加 1。如果当前孩子的评分低于前一个孩子的评分，它会从后往前找到第一个评分高于当前孩子的孩子，并将该孩子的糖果数增加 1。最后，它计算并返回糖果总数。

这段代码的时间复杂度为 O(n)，其中 n 是孩子的数量，因为它只需要遍历评分数组一次。空间复杂度也为 O(n)，因为它需要创建一个新的列表来存储每个孩子的糖果数。

(文章为作者在学习java过程中的一些个人体会总结和借鉴，如有不当、错误的地方，请各位大佬批评指正，定当努力改正，如有侵权请联系作者删帖。)