Greedy The best choice now
498. Candy
Children stand in a row, and each child has a rating. You are given the ratings as an array ratings, where
ratings[i] is the rating of the child at position i.
You hand out candies under two rules:
- Every child gets at least one candy.
- A child with a higher rating than a neighbour gets more candies than that neighbour.
Return the fewest candies you need in total.
A child's neighbours are the children directly to its left and right. The rules say nothing about two neighbours with the same rating, so either of them may get more.
Example 1
Input: ratings = [2, 5, 4, 3, 3, 1]
10Explanation: The children get 1, 3, 2, 1, 2 and 1 candies. The child rated 5 needs more than the 4 beside it, and the 4 needs more than the 3. The two children rated 3 stand together, so the second can have 2 while the first has 1.
Example 2
Input: ratings = [7, 7, 7, 7]
4Explanation: Every rating is the same, so no child needs more than a neighbour. One candy each is enough.
Example 3
Input: ratings = [10, 8, 5, 0, 0]
11Explanation: The children get 4, 3, 2, 1 and 1. The ratings fall from the first child to the fourth, so the candies must fall too. The last two children tie and get 1 each.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ ratings.length ≤ 1050 ≤ ratings[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.