首页 > 代码库 > [Leetcode][JAVA] Candy

[Leetcode][JAVA] Candy

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?

 

在遍历数组的过程中,大致可以分为三种情况:1. 后一个孩子得分比前一个孩子高; 2. 得分一样; 3. 得分比前一个孩子低。

对于第一种情况,糖果数只要多给前一个孩子所得的糖果数+1 即可。比如C[i-1]给了X糖果, C[i]应该给X+1糖果。这里需要一个变量curCandy记录前一个孩子的糖果数X。

第二种情况,根据题目意思,只有higher rating的孩子才能拿比周围人多的糖果,那么如果得分一样即可以随意分配。为了使总数尽量少,应给新遍历到的孩子1个糖果(总糖果数+1).

第三种情况比较复杂。这里使用一个例子来说明:

假设孩子的评分按顺序如下:

ratings: 1 2 5 4 3 2 1

index: 0 1 2 3 4 5 6

Candy[i]表示遍历到第i个孩子后应分配糖果总数的增量

根据情况1,Candy[0]=1, Candy[1]=2, Candy[2]=3

第3号孩子来的时候,由于得分比第二号孩子少,为了总数尽量少,应该分给3号孩子1个糖果,Candy[3]=1

第4号孩子来的时候,理应比3号孩子拿的糖果少,但3号孩子已经只拿1个了,所以需要调整3号孩子的糖果数,让3号多拿一个,然后4号拿1个糖果。问题在于,3号多拿1个糖果,会不会跟2号有冲突?在这里,2号拿了3个糖果,如果3号多拿1个(即为2个糖果)也不会产生冲突。

所以Candy[4]=2 (4号拿1个糖果,3号补发1个糖果)

当第5号孩子来的时候,同理要给3号和4号补发糖果,但是这样的话3号的糖果就到了3个,跟2号一样了,这是不允许的,所以还得给2号再补发一个糖果。

所以Candy[5]=4 (5号拿1个糖果,2,3,4号各补发一个糖果)。

同理Candy[6]=5

 

在分析第三种情况的过程中,我们需要知道这些信息: 1. 顺势给前面孩子补发糖果,补发到哪个孩子为止? 2. 什么时候需要多给一个孩子补发糖果(例子中遍历到5号时,需要给2号补发糖果,但遍历到4号时不需要)

对于问题1,答案是最多补发到之前最近的得分比前一个孩子高或者一样的孩子(峰值),记为Top。对于问题2,如果Top所得的糖果跟后一个孩子一样了,需要多给Top补发。

所以需要两个变量,index记录Top的下标,capacity记录Top得到的糖果。

而增量可以简单地用i-index或i-index+1来表示,比如Candy[3]=1, 此时index为2,这个1可以用i-index (即:3-2)算出.

同理Candy[4]= i-index = 4-2 = 2

Candy[5]原本应该等于i-index=3.但是capacity为3,i-index=capacity意味着需要多给一个孩子补发,所以Candy[5]=i-index+1=4

同理Candy[6]=5

然后总糖果数即为Sum(Candy[0~6])

最后,需要注意的是如果遇到相同ratings的孩子, index也需要移到最后一个孩子上,capacity记录的也是最后一个孩子的拿的糖果数。

代码如下:

 1 public int candy(int[] ratings) { 2         int re = 1; 3         int curCandy = 1; 4         int index = 0; 5         int capacity = 1; 6         for(int i=1;i<ratings.length;i++) { 7             if(ratings[i]>ratings[i-1]) { 8                 index = i; 9                 curCandy++;10                 capacity = curCandy;11                 re += curCandy;12             }13             else if(ratings[i]==ratings[i-1]) {14                 index=i;15                 re += 1;16                 curCandy=1;17                 capacity=1;18             }19             else if((i-index)<capacity) {20                 re += i-index;21                 curCandy=1;22             }23             else {24                 re += i-index+1;25                 curCandy=1;26             }27         }28         return re;29     }

 

[Leetcode][JAVA] Candy