Candy
Hard · greedy
A teacher has a row of children, and ratings[i] is how well child i did in a test.
She hands out sweets under two rules:
- Every child gets at least one sweet.
- If a child has a strictly higher rating than the child directly to their left or right, they must get more sweets than that neighbour. Children with equal ratings may get any amounts.
Return the smallest total number of sweets she has to hand out.
Examples
Example 1
Input: ratings = [2, 5, 3, 3, 1]
Output: 7
Give 1, 2, 1, 2, 1. The child with rating 5 beats both neighbours, so gets 2. The first child with rating 3 gets 1. The second one beats the child with rating 1, so gets 2.
Example 2
Input: ratings = [4, 4, 4]
Output: 3
Nobody has a higher rating than a neighbour, so one sweet each is enough.
Example 3
Input: ratings = [1, 2, 3, 4]
Output: 10
Each child beats the one on their left, so the sweets must be 1, 2, 3, 4.
Constraints
- 1 <= len(ratings) <= 10^4
- 0 <= ratings[i] <= 10^5