当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--38--分发糖果(Java)
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
注:题目没有讲清如果两个小孩子分数相等的情况如何分配糖果数，
在题解当中是后一个小孩子分配的糖果数要少于或者等于前一个相同分数的小孩子.
比如：
输入：[2,2,2,2,2] 答案：5。每个小孩子分配1个
输入：[1,3,3,4,5] 答案：9。分配规则：1、2、1、2、3
(题目来源：力扣（LeetCode）)
1.贪心算法
思路：分数数组中有三种可能：升序、平序、降序（对应不同的处理办法），我们分别对这三个贪心就好了，按照这三种序列遍历完即可得到对应的总糖果数
package com.lxf.test;
public class Candy {
public static void main(String[] args) {
//1,0,2,4,2,6,7,9,5,3
//1,3,2,2,1
//1,0,2
//1,2,87,87,87,2,1
System.out.println(candy(new int[]{0}));
}
public static int candy(int[] ratings) {
//糖果数
int candyNum=0;
//升序基数
int base1=1;
//降序基数
int base2=0;
int length=ratings.length-1;
if(length<0) return 0;
if(length==0) return 1;
for (int i = 0; i < length; ) {
//升序处理，candyNum直接++（注意：没包含第一个数字）
//第一个数字放到降序中处理，而第一次升序特殊(前面没有降序队列)
//注意此时糖果数已经将下一个降序队列的第一个数字加上了
while(i<length &&ratings[i]<ratings[i+1]){
candyNum+=++base1;
i++;
}
//第一次升序需+1
if(base1==i+1&&candyNum>0){
candyNum+=1;
}
//如果是平序,直接+1，也有注意：开头平序和全部数字平序特殊需+1
while(i< length&&ratings[i]==ratings[i+1]){
candyNum+=1;
base1=1;
i++;
}
//降序处理，base2++
while(i< length&&ratings[i]>ratings[i+1]){
base2++;
i++;
}
//从base2一直加到1,就相当于将降序队列全部包括
//比如:1、2、3、6、5、4、3、2、1、4、7
//其中6 5 4 3 2 1为降序队列，这种方法确保降序全部包含，也包含了下一次升序队列（1，4，7）的1
int k=base2;
while (k>0){
candyNum+=k;
k--;
}
if(base2!=i){
//不是第一次降序就要判断是否超过了前面队列的最后一个值
//比如分数数组：1 2 5 4 3 2 1
//前一步分配糖果数为: 1 2 3 4 3 2 1
//5分数对应糖果数为3
//4分数对应糖果数为4。这不符合规则
//5需要增加糖果数:
//此时base1对应就是5的糖果数.而base2对应的就是4的糖果数
//base2-base1+1就是5需要增加的糖果数(确保分数高的分到的糖果数越多)
candyNum+=base2<base1?0:base2-base1+1;
}else{
//第一次降序需加上开头第一个数字
candyNum+=i+1;
}
//将降序和升序置回
base2=0;
base1=1;
}
if(ratings[0]==ratings[1]){
//开头平序和全部数字平序特殊需+1
candyNum+=1;
}
return candyNum;
}
}
我们注意到：第一次升序或平序都会丢个1，而第一次降序丢个i+1，我们把i+1改成i,不就什么情况都要加1了嘛，最后将糖果数初始值置为1即可。
2.贪心算法小优化：
package com.lxf.test;
public class Candy {
public static void main(String[] args) {
//1,0,2,4,2,6,7,9,5,3
//1,3,2,2,1
//1,0,2
//1,2,87,87,87,2,1
System.out.println(candy(new int[]{0}));
}
public static int candy(int[] ratings) {
//糖果数
int candyNum=1;
//升序基数
int base1=1;
//降序基数
int base2=0;
int length=ratings.length-1;
if(length<0) return 0;
if(length==0) return 1;
for (int i = 0; i < length; ) {
//升序处理，candyNum直接++（注意：没包含第一个数字）
//第一个数字放到降序中处理，而第一次升序特殊(前面没有降序队列)
//注意此时糖果数已经将下一个降序队列的第一个数字加上了
while(i<length &&ratings[i]<ratings[i+1]){
candyNum+=++base1;
i++;
}
//如果是平序,直接+1，也有注意：开头平序和全部数字平序特殊需+1
if(i< length&&ratings[i]==ratings[i+1]){
candyNum+=1;
base1=1;
i++;
}
//降序处理，base2++
while(i< length&&ratings[i]>ratings[i+1]){
base2++;
i++;
}
//从base2一直加到1,就相当于将降序队列全部包括
//比如:1、2、3、6、5、4、3、2、1、4、7
//其中6 5 4 3 2 1为降序队列，这种方法确保降序全部包含，也包含了下一次升序队列（1，4，7）的1
int k=base2;
while (k>0){
candyNum+=k;
k--;
}
if(base2!=i){
//不是第一次降序就要判断是否超过了前面队列的最后一个值
//比如分数数组：1 2 5 4 3 2 1
//前一步分配糖果数为: 1 2 3 4 3 2 1
//5分数对应糖果数为3
//4分数对应糖果数为4。这不符合规则
//5需要增加糖果数:
//此时base1对应就是5的糖果数.而base2对应的就是4的糖果数
//base2-base1+1就是5需要增加的糖果数(确保分数高的分到的糖果数越多)
candyNum+=base2<base1?0:base2-base1+1;
}else{
//第一次降序需加上开头第一个数字(本来是i+1,改成i，保证了第一次不管是哪种序列都要丢个1)
candyNum+=i;
}
//将降序和升序置回
base2=0;
base1=1;
}
return candyNum;
}
}
3. 两次遍历（官方题解）
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
//存储左规则数(也即升序)，匹配到右规则不赋值按平序-->1
int[] left = new int[n];
for (int i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
//平序数
left[i] = 1;
}
}
//right:左规则(匹配降序)，匹配到左规则不赋值按平序-->1
//ret：总糖果数
int right = 0, ret = 0;
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1 && ratings[i] > ratings[i + 1]) {
right++;
} else {
//平序数
right = 1;
}
//增加右规则(包含平序)和左规则(包含平序)的最大值(很妙)
//这一句相当于贪心算法的三段浓缩
ret += Math.max(left[i], right);
//比如一个分值数组:1 2 3 3 5 7 6 4 2
//left数组： 1 2 3 1 2 3 1 1 1
//right变量：1 1 1 1 1 4 3 2 1
