[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.

============Solved============
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顆糖果,
這樣,只要從左到右,再從右到左,各掃一次就可以得到每個孩子的糖果數量。
步驟1. 左到右
可以從ratings[1](並非ratings[0])往右掃一次並比大小,如果當前的分數大於左邊的分數,則當前的這個小朋友的糖果會比左邊的小朋友多1顆(因為一開始假設大家都有1顆)
步驟2. 右到左
從最ratings[length-1]這個小朋友往左邊掃,直到第1個小孩(ratings[1]),如果左邊的分數大於當前的孩子的分數,則當前孩子的糖果+1與左邊孩子的糖果取最大值後即為左邊孩子的糖果數量
同時開始累計從candies[length-1]至cnadies[1]的糖果數量
步驟3. 把左0的糖果加進去
因為從右到左掃過去的時候,candies[0]的糖果可能在最後一輪才更改數量,所以最後才能把candies[0]的糖果加進去,而不是在掃完左到右的時候就開始把candies[0]設為count的初始值。