郑州网站建设制作谷歌广告
🏆作者简介，普修罗双战士，一直追求不断学习和成长，在技术的道路上持续探索和实践。
🏆多年互联网行业从业经验，历任核心研发工程师，项目技术负责人。
🎉欢迎 👍点赞✍评论⭐收藏
算法专栏学习
| 题目 | 访问地址 | 专栏 |
|---|---|---|
| 分发糖果 | https://blog.csdn.net/m0_50308467/article/details/135343315 | 算法专栏 |
经典算法题 之 分发糖果
题目如下：
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
解答这道题，可以使用
贪心算法进行解决。
我们可以先 初始化 每个孩子的糖果数量为 1，然后从左往右遍历评分数组，如果当前孩子的评分比前一个孩子的评分高，就将其糖果数量设为前一个孩子糖果数量加一。这样可以确保相邻两个评分高的孩子分配到的糖果数量相差至少为1。
但是我们还需要从右往左遍历一遍评分数组，来处理相邻两个评分高的孩子分配到的糖果数量相等的情况。如果当前孩子的评分比后一个孩子的评分高，且当前孩子的糖果数量不大于后一个孩子的糖果数量，就将其糖果数量设为后一个孩子糖果数量加一。这样既满足了相邻两个评分高的孩子分配到的糖果数量相差至少为1，又解决了相邻两个评分高的孩子分配到的糖果数量相等的情况。
最后，我们把每个孩子的糖果数量累加起来，就可以得到需要准备的最少糖果数目。
具体实现逻辑如下：
1. 首先创建一个与评分数组大小相同的糖果数组，初始化为1，表示每个孩子至少分配到一个糖果。
2. 从左到右遍历评分数组，如果当前孩子的评分比前一个孩子高，那么将当前孩子的糖果数目设为前一个孩子糖果数目加1。
3. 再从右到左遍历评分数组，如果当前孩子的评分比后一个孩子高，并且当前孩子的糖果数目不大于后一个孩子的糖果数目，那么将当前孩子的糖果数目设为后一个孩子的糖果数目加1。
4. 最后计算糖果数组的总和，即为最少糖果数目。
以下是一个Java代码实现：
public class DistributeCandies {public static int distributeCandies(int[] ratings) {int n = ratings.length;int[] candies = new int[n];Arrays.fill(candies, 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] && candies[i] <= candies[i+1]) {candies[i] = candies[i+1] + 1;}}// 统计总的糖果数int sum = 0;for (int candy : candies) {sum += candy;}return sum;}// 示例调用public static void main(String[] args) {int[] ratings = {1,0,2};System.out.println(distributeCandies(ratings)); // 输出3}
}
在这个示例中，distributeCandies() 方法接收一个评分数组 ratings ，并返回需要准备的最少糖果数目。
首先，我们使用一个长度为 n 的数组 candies 来保存每个孩子的糖果数量，初始值都为 1。
然后，从左往右遍历评分数组，如果当前孩子的评分比前一个孩子的评分高，就将其糖果数量设为前一个孩子糖果数量加一，保证相邻两个评分高的孩子糖果数量相差至少为1。
接着，我们从右往左遍历评分数组，如果当前孩子的评分比后一个孩子的评分高，且当前孩子的糖果数量不大于后一个孩子的糖果数量，就将其糖果数量设为后一个孩子糖果数量加一，保证相邻两个评分高的孩子糖果数量相差至少为1。
最后，我们把每个孩子的糖果数量累加起来，得到需要准备的最少糖果数目。
在 main() 方法中，我们提供了一个简单的测试案例，将评分数组设为 [1,0,2]，调用 distributeCandies() 方法进行计算，期望的输出为3。
