想要精通算法和SQL的成长之路 - 分发糖果

• 前言
• 一. 分发糖果
• • 1.1 贪心法分析
  • 1.2 最终完整代码

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 分发糖果

原题链接

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

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

• 输入: [1,0,2]
• 输出: 5
• 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

1.1 贪心法分析

思路：我们用candy[i]代表这个孩子拥有的糖果数。初始化时，每个小朋友有一个糖果。

int[] candy = new int[ratings.length];
Arrays.fill(candy, 1);

先从左往右遍历：

• 只考虑右侧评分大于左侧评分的孩子，给他多分一个糖果。（局部最优）
• 此时能保证，相邻的两个孩子，右侧孩子的糖果数一定 >= 左侧孩子的糖果数。
• 如果右侧孩子评分更高，那么他的糖果数应该是左侧孩子的糖果数candy[i] + 1。

for (int i = 0; i < ratings.length - 1; i++) {// 右侧孩子评分比左侧孩子高if (ratings[i + 1] > ratings[i]) {candy[i + 1] = candy[i] + 1;}
}

再从右往左遍历：

• 只考虑左侧评分大于右侧评分的孩子。那么此时需要保证左侧孩子的糖果数一定要保证比右侧大。（局部最优）

那么此时有两种可能：

• 第一种：candy[i]（左侧） < candy[i+1]（右侧），那么左侧孩子的的糖果数应该是candy[i+1]+1。
• 第二种：candy[i]（左侧） > candy[i+1]（右侧），那么左侧孩子的的糖果数应该是candy[i]。因为已经满足条件了，不用再给他了。

总结就是candy[i] = Math.max(candy[i],candy[i+1]+1)

for (int i = ratings.length - 2; i >= 0; i--) {// 左侧孩子评分比右侧孩子高if (ratings[i] > ratings[i + 1]) {candy[i] = Math.max(candy[i], candy[i + 1] + 1);}
}

同时满足两个局部最优，那么最终结果就是全局最优了。

1.2 最终完整代码

public int candy(int[] ratings) {int[] candy = new int[ratings.length];// 初始化糖果，让每个孩子都至少有1个。Arrays.fill(candy, 1);// 第一次从左往右遍历for (int i = 0; i < ratings.length - 1; i++) {// 右侧孩子评分比左侧孩子高if (ratings[i + 1] > ratings[i]) {candy[i + 1] = candy[i] + 1;}}// 第二次从右往左遍历for (int i = ratings.length - 2; i >= 0; i--) {// 左侧孩子评分比右侧孩子高if (ratings[i] > ratings[i + 1]) {candy[i] = Math.max(candy[i], candy[i + 1] + 1);}}return Arrays.stream(candy).sum();
}