dsa · hard
Candy
There are n children in a line. ratings[i] is child i's rating. You must give each child at least one candy. If a child has a strictly higher rating than a neighbor (left or right), that child must receive strictly more candies than that neighbor. Return the minimum total number of candies that satisfies both rules.
Arguments
ratings— child i's rating; higher than a neighbor means more candies than that neighbor
Example
ratings = [1,0,2]. The middle child has the lowest rating and can take 1 candy. Each side is higher than the middle, so each needs at least 2. Total 2 + 1 + 2 = 5.
ratings = [1,2,2]. The first child takes 1. The second is higher than the first, so takes 2. The third is equal to the second (not strictly higher), so 1 is enough. Total 4.
ratings = [1,2,3,4,5] is strictly increasing, so candies 1,2,3,4,5 sum to 15.
Constraints
1 <= ratings.length <= 4*10^4 0 <= ratings[i] <= 2*10^4 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [1,0,2] Expected: 5
Example 2
Input: [1,2,2] Expected: 4
Example 3
Input: [1,2,3,4,5] Expected: 15