leetcode135. Candy

2018-03-01 11:14:17来源:segmentfault作者:raledong人点击

分享
题目要求
There are N children standing in a line. Each child is assigned a rating value.You are giving candies to these children subjected to the following requirements:Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

假设有N个孩子站成一排,每个孩子拥有一个评估值。现在要根据以下的需求给孩子们分发糖果:

每个孩子至少有一颗糖
有更高评估值的孩子应当比两侧孩子得到的糖更多

问最少要发出多少颗糖?


思路和代码

这里我们可以举一个例子来先试着分配一下:
假设有10个孩子,每个孩子对应的评估分别是[3,4,5,7,2,3,3,2,1,10]
按照尽量少分配的原则,前四个孩子我们会分别给1,2,3,4颗糖,从第五个孩子开始,我们只需要给1颗糖就可以满足需求。


前五个孩子的分配情况如下:
[1,2,3,4,1, , , , , ]


第六个孩子和第七个孩子评估值相同,我们还是可以将第七个孩子赋值1,因为这样还是可以满足要求。结果如下:
[1,2,3,4,1,2,1, , , ]


到第八个孩子的时候,我们发现这个孩子评估值比第七个孩子低,但是基于每个孩子最少一颗糖的原理,我们必须给第八个孩子一颗糖并且开始回调前面分发的糖的数量。
[1,2,3,4,1,2,2,1, , ]


第九个孩子的情况一样,我们同样给他一颗糖并调整:
[1,2,3,4,1,2,3,2,1, ]


最后孩子评分比前一个评分高,我们只需直接在前一个孩子的数量上加1即可:
[1,2,3,4,1,2,3,2,1,2]


由此我们可以总结出以下几个结论:

当后一个孩子比前一个孩子评分高时,直接在前一个孩子糖果数量基础上加1

当后一个孩子比前一个孩子评分低时

前一个孩子糖果数量大于1,则该孩子糖果数量为1
前一个孩子糖果数量为1,则该孩子糖果数量为1,并且将前面相应孩子的糖果数量加1
当后一个孩子和前一个孩子评分一样多,则该孩子糖果数量为1

这是我们只需要知道,当后一个孩子比前一个孩子评分低,且前一个孩子糖果数量为1时,最少由多少个孩子需要额外分发一个糖果。我们可以观察到,每次最远只需要额外分发到距离当前最近的评分最高的那个孩子。因为他的糖果数量的增加并不会影响到之前孩子。
至于该评分最高的孩子是否需要增加糖果,则要看后面的孩子增加后的糖果数量是不是比他高。


当有多个最近评分最高的孩子时,则选择最后一个。


代码如下:


public int candy(int[] ratings) {
int count = 1;
int summitIndex = 0;
int summitCandy = 1;
int prevCandy = 1;
for(int i = 1 ; i<ratings.length ; i++){
if(ratings[i] > ratings[i-1]){
prevCandy++;
count += prevCandy;
summitIndex = i;
summitCandy = prevCandy;
}else if(ratings[i] < ratings[i-1]){
if(prevCandy == 1){
count += (i - summitIndex) + (i-summitIndex >= summitCandy ? 1 : 0);
}else{
prevCandy = 1;
count += prevCandy;
}
}else{
prevCandy = 1;
count += prevCandy;
summitIndex = i;
summitCandy = prevCandy;
}
}
return count;
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台