[Java][Greedy][LeetCode] Candy #135

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

The question requires that if the score is higher than neighbors, he will have more candies than the neighbors.
Each child must have at least one candy.
In this way, I scan from left to right and then from right to left, I can get candies for each child.
Step 1. Left to right
I scan from ratings[1] (not ratings[0]) to the right and compare the number. If the current score is higher than the score on the left, the current kid’s candy will be 1 more than the kid on the left (because it was assumed at the beginning Everyone has 1)
Step 2. Right to left
I scan from ratings[length-1] to the left, until the first child (ratings[1]). If the score on the left is higher than the score of the current child, compare current kid’s candy +1 and left kid’s candy who is more and to get max, the left kid’s candy is max.
At the same time start to accumulate the number of candies from candies[length-1] to candies[1]
Step 3. Add candies[0]
Because when scanning from right to left, the number of candies in candies[0] may not be changed until the last round, candies[0] maybe will be edited in the end. Instead of scan left to right finish. initial count is 0 not candies[0].
步驟1. 左到右
步驟2. 右到左
步驟3. 把左0的糖果加進去