Description
There are n children standing in a line. Each child has a rating value in the ratings array. You are giving candies to these children with two rules: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum candies you must give.
Examples
Input:
ratings = [1,0,2]Output:
5Explanation:
Give 2, 1, 2 candies respectively.
Input:
ratings = [1,2,2]Output:
4Explanation:
Give 1, 2, 1 candies. Third child gets 1 since ratings[1] == ratings[2].
Input:
ratings = [5,4,3,2,1]Output:
15Explanation:
This is a strictly decreasing sequence. Starting from the right with 1 candy for the lowest rating, each child to the left needs one more candy than their right neighbor: [5,4,3,2,1] candies respectively. Total: 5+4+3+2+1 = 15.
Constraints
- •
n == ratings.length - •
1 ≤ n ≤ 2 × 10⁴ - •
0 ≤ ratings[i] ≤ 2 × 10⁴