# [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的初始值。