Loading problem…
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: Give the children 2, 1 and 2 candies. The middle child has the lowest rating, so gets 1, and each neighbour has a higher rating, so each needs 2. The total is 5.
Example 2
Input: ratings = [1,2,2]
Output: 4
Explanation: Give 1, 2 and 1 candies. The second child outranks the first, so needs 2. The third child has the same rating as the second, so only needs 1. The total is 4.
Example 3
Input: ratings = [1,3,2,2,1]
Output: 7
Explanation: Give 1, 2, 1, 2, 1 candies. Rating 3 beats both neighbours, the second 2 beats the final 1, and equal ratings impose no rule. The total is 7.
Satisfy the left neighbor rule and the right neighbor rule separately. First sweep left to right giving a child one more candy than its left neighbor when it's rated higher; then sweep right to left doing the same for the right neighbor, taking the maximum so both rules hold.
Run checks all cases above. Submit evaluates all test cases.