- 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 | class Solution { |

我的代码实现：

1 | class Solution { |

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

A simple solution

1 | class Solution { |

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 | class Solution { |

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 | class Solution { |

#### python

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

Simple python solution with two passes

1 | class Solution: |

#### java

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

Simple O(n) Java solution with comments

1 | public class Solution { |

1 | public int candy(int[] ratings) { |

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:

- His/her rating is equal to the previous one -> give 1 candy.
- His/her rating is greater than the previous one -> give him (previous + 1) candies.
- 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 | public static int candy(int[] ratings) { |

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 | ratings: [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 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 | ratings: [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 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 | ratings: [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1] |

Total minimum candies: 23

1 | public int candy(int[] ratings) { |