111. Candy

Hard · Array

There are n children sitting in a line. Each child is assigned a rating value given in the array ratings. You are distributing candies to these children such that each child must receive at least one candy. Children with a higher rating than their neighbors must receive more candies than those neighbors. Determine the minimum number of candies you need to distribute.

Examples

Example 1
Input: [1, 0, 2]
Output: 5
Explanation: Ratings are [1, 0, 2]. Child at index 1 has the lowest rating (0), so give 1 candy. Child at index 0 has rating 1 > 0, so give 2 candies. Child at index 2 has rating 2 > 1, so give 3 candies. Total: 1 + 2 + 3 = 6. However, we can optimize: give [2, 1, 2] for a total of 5 candies, where child 0 gets 2 (higher than neighbor 1), child 1 gets 1 (lowest), and child 2 gets 2 (higher than neighbor 1).
Example 2
Input: [1, 2, 3, 4, 5]
Output: 15
Explanation: Ratings are strictly increasing. Each child must have more candies than the previous: [1, 2, 3, 4, 5]. Total: 1 + 2 + 3 + 4 + 5 = 15.

Constraints