Candy
HardP3Coding
n children stand in a line, child i having rating ratings[i]. Give each child at least one candy so that a child with a higher rating than a neighbour (left or right) gets strictly more candy than that neighbour. Return the minimum total number of candies.
Example 1
- Input
- ratings = [1,0,2]
- Output
- 5
- Why
- Give 2, 1, 2 candies.
Example 2
- Input
- ratings = [1,2,2]
- Output
- 4
- Why
- Give 1, 2, 1: equal ratings do not force more candy.
Constraints
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.