135. Candy

  • 24.2%

https://leetcode.com/problems/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?


方法一:

A simple solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int candy(vector<int>& ratings) {
int size = ratings.size();
if(size<=1) return size;
vector<int> ret(size, 1);
for(int i=1; i<size; i++){
if(ratings[i]>ratings[i-1])
ret[i] = ret[i-1]+1;
}
for(int i=size-1; i>0; i--){
if(ratings[i-1]>ratings[i])
ret[i-1] = max(ret[i-1], ret[i]+1);
}
int result = 0;
for(int i=0; i<size; i++)
result += ret[i];
return result;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int candy(vector<int>& ratings) {
auto n = ratings.size();
if(n==1) return 1;
vector<int> v(n, 1);
for(int i=1; i<n; i++){
if(ratings[i]>ratings[i-1])
v[i] = v[i-1]+1;
}
for(int i=n-2; i>=0; i--){
if(ratings[i]>ratings[i+1])
v[i] = max(v[i], v[i+1]+1);
}
int res = 0;
for(int i=0; i<n; i++)
res += v[i];
return res;
}
};

https://discuss.leetcode.com/topic/5243/a-simple-solution

A simple solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int candy(vector<int>& ratings) {
int size = ratings.size();
if(size<=1) return size;
vector<int> ret(size, 1);
for(int i=1; i<size; i++){
if(ratings[i]>ratings[i-1])
ret[i] = ret[i-1]+1;
}
for(int i=size-1; i>0; i--){
if(ratings[i-1]>ratings[i])
ret[i-1] = max(ret[i-1], ret[i]+1);
}
int result = 0;
for(int i=0; i<size; i++)
result += ret[i];
return result;
}
};

https://discuss.leetcode.com/topic/17722/two-c-solutions-given-with-explanation-both-with-o-n-time-one-with-o-1-space-the-other-with-o-n-space

Two C++ solutions given with explanation (both with O(N) time, one with O(1) space, the other with O(N) space)

The question requires us to make sure a child with a higher rate has more candies than its left and right neighbors. One simple solution is to do two scans: one foward scan (from 1 to N-1) to make sure child i has more candies than its left neighbor if its rate is higher than its left neighbor. After the forward scan, we can guarantee that the left neighbor relationship is correct but we have to do more to make the right neighbor relationship in order; so we do the backwarad scan (from N-2 to 0) to make child i has more candies than its right neighbor i+1 if its rate is higher than its right neighbor. In the following implementation, we need a O(N) array number to save the number of candies needed for children, so it has O(N) space complexity and we do two linear scans so the time complexity is O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int candy(vector<int>& ratings) {
int len = ratings.size(), res = 0, i;
if(len>0)
{
vector<int> number(len,0); // to save the number of candies for child[0:N-1]
number[0] = 1;
// forward scan to calculate how many candies needed for child i to make sure it has more candies than its left neighbor if it has a higher rate, otherwise, give one candy to it
for(i=1; i<len;++i) number[i] = ratings[i]>ratings[i-1]?number[i-1]+1:1;

// backward scan to calculate to make sure child i has more candies than its right neighbor if it has a higher rate, pick the bigger one from forward and backward scans as the final number for child i
for(i=len-2, res = number[len-1]; i>=0;--i)
{
if( (ratings[i]>ratings[i+1]) && number[i]<(number[i+1]+1) ) number[i] = number[i+1]+1;
res += number[i];
}
}
return res;
}
};

Now, the question is can we do better? Do we really need two scans? If we do only forward scan, then the problem is we can not guarantee the right neighbor relationship holds. i.e. we don’t know if the following order is descending (i>i+1>i+2>…). and that may cause issues. To fix that, we will detect the dips (the points at which the order switchs from increasing to decreasng). We will make sure all the local dips (minimum points) has only one candy and update its previous neighbors (which has hgher rates than its rate) accordingly. To do such update, we need to know when the decrease starts, so we use pPos to save that starting points.
So the solution becomes: do the forward scan, if it is in an increasing order (child i rate > child i-1 order), check if it is a local dip (neg_peak == true): if so, update the candy number to make sure child i-1 has one candy. if not, just give one more candy to child i. If it is in an decreasing order (child i rate < child i-1 order)
, just give one less candy to i. don’t forget at last, we still need to make sure child N-1 has one or more candy. So O(1) space , O(N) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
int candy(vector<int>& ratings) {
const int len = ratings.size();
if(len<=1) return len;

int i, pPos, res=1, peak=1; // peak: # candies given to the i-1 child
bool neg_peak = false; // flag to indicate if it is a local dip
for(i=1; i<len;i++)
{
if(ratings[i] >= ratings[i-1])
{ // it is increasing
if(neg_peak)
{ // it is a local dip, we need to make sure i-1 has one candy
res -= (peak-1) * (i-pPos - (peak>0));
peak = 1;
neg_peak = false;
}
// update child i candy number, if equal, set to 1
peak = (ratings[i] == ratings[i-1])? 1:++peak;
res += peak;
}
else
{ // decreasing, just give one less candy, if it is the starting point of a decrease, update pPos
if(!neg_peak) {pPos = i-1; neg_peak = true;}
res += --peak;
}
}// don't forget to update res, if the last one is a local dip
return !neg_peak? res : res - (peak-1) * (i-pPos - (peak>0));

}
};

python


https://discuss.leetcode.com/topic/21025/simple-python-solution-with-two-passes

Simple python solution with two passes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
# @param {integer[]} ratings
# @return {integer}
def candy(self, ratings):
# use two pass scan from left to right and vice versa to keep the candy level up to now
# similar to like the Trapping Rain Water question
res = [1]*len(ratings) # also compatable with [] input
lbase = rbase = 1
# left scan
for i in xrange(1, len(ratings)):
lbase = lbase + 1 if ratings[i] > ratings[i-1] else 1
res[i] = lbase
# right scan
for i in xrange(len(ratings)-2, -1, -1):
rbase = rbase + 1 if ratings[i] > ratings[i+1] else 1
res[i] = max(rbase, res[i])
return sum(res)

java


https://discuss.leetcode.com/topic/25985/simple-o-n-java-solution-with-comments

Simple O(n) Java solution with comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int candy(int[] ratings) {
int candies[] = new int[ratings.length];
Arrays.fill(candies, 1);
for(int i=1; i<ratings.length; i++)
if(ratings[i]>ratings[i-1])
candies[i] = candies[i-1] + 1;
for(int i=ratings.length-1; i>0; i--)
if(ratings[i-1]>ratings[i])
candies[i-1] = Math.max(candies[i-1], candies[i]+1);
int result = 0;
for(int i=0; i<ratings.length; i++)
result += candies[i];
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int candy(int[] ratings) {
int candies[] = new int[ratings.length];
Arrays.fill(candies, 1);// Give each child 1 candy

for (int i = 1; i < candies.length; i++){// Scan from left to right, to make sure right higher rated child gets 1 more candy than left lower rated child
if (ratings[i] > ratings[i - 1]) candies[i] = (candies[i - 1] + 1);
}

for (int i = candies.length - 2; i >= 0; i--) {// Scan from right to left, to make sure left higher rated child gets 1 more candy than right lower rated child
if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], (candies[i + 1] + 1));
}

int sum = 0;
for (int candy : candies)
sum += candy;
return sum;
}

https://discuss.leetcode.com/topic/8208/one-pass-constant-space-java-solution

One-pass constant space Java solution

This solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:

  1. His/her rating is equal to the previous one -> give 1 candy.
  2. His/her rating is greater than the previous one -> give him (previous + 1) candies.
  3. His/her rating is less than the previous one -> don’t know what to do yet, let’s just count the number of such consequent cases.

When we enter 1 or 2 condition we can check our count from 3. If it’s not zero then we know that we were descending before and we have everything to update our total candies amount: number of children in descending sequence of raitings - coundDown, number of candies given at peak - prev (we don’t update prev when descending). Total number of candies for “descending” children can be found through arithmetic progression formula (1+2+…+countDown). Plus we need to update our peak child if his number of candies is less then or equal to countDown.

Here’s a pretty concise code below.

详情参考以下链接:
http://www.allenlipeng47.com/blog/index.php/2016/07/21/candy/

But there is a O(n) time, O(1) space solution, which is pretty hard to understand. Let me try to explain this O(1) space solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int candy(int[] ratings) {
int pre = 1, countDown = 0, total = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] >= ratings[i - 1]) {
if (countDown > 0) {
total += countDown * (countDown + 1) / 2; // progression part
if (countDown >= pre) { // check if pre is tall enough
total += countDown - pre + 1;
}
pre = 1; // when ascending and there is countDown, prev should be 1
countDown = 0;
}
pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1; // when equals to previous one, set to 1. Else set to prev + 1
total += pre;
}
else {
countDown++;
}
}
if (countDown > 0) { // check if there is countDown in the end
total += countDown * (countDown + 1) / 2;
if (countDown >= pre) {
total += countDown - pre + 1;
}
}
return total;
}


https://discuss.leetcode.com/topic/37924/very-simple-java-solution-with-detail-explanation

Very Simple Java Solution with detail explanation

1
We take ratings array as [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]

In the given problem each student will have at least 1 candy. So distribute 1 candy to each.

1
2
ratings:     [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
candies: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Now traverse the array from left to right. If the rating of (n+1) child is greater than (n) child then set the candy of (n+1) child as one candy more than the (n) child candies.

1
2
ratings:     [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
candies: [1, 2, 1, 1, 2, 3, 4, 1, 1, 1, 2, 1]

Now traverse the array from right to left. If the (n) child rating is more than (n+1) child and (n) child candies is less than one more than (n+1) child candies then update the candies of (n) child as 1+ (n+1) candies.

1
2
ratings:     [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
candies: [1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 2, 1]

Total minimum candies: 23

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

谢谢你,可爱的朋友。