Distributing Candies Fairly

Imagine you have a line of children, and you want to give them candies. You have a specific set of rules for distributing these candies to ensure fairness and reward children based on their performance. This challenge involves determining the minimum number of candies required to satisfy these distribution rules.

Problem Description

You are given a list representing the ratings of N children standing in a line. You need to distribute candies to these children such that:

1. Every child must have at least one candy.
2. Children with a higher rating get more candies than their neighbors.

Your goal is to find the minimum total number of candies you need to distribute.

Examples

Example 1:

Input: [1, 0, 2]
Output: 5
Explanation: You can give the first child 1 candy, the second child 1 candy, and the third child 2 candies. This satisfies all conditions:
- Child 1 (rating 1) gets 1 candy.
- Child 2 (rating 0) gets 1 candy.
- Child 3 (rating 2) gets 2 candies.
Child 1 has a higher rating than Child 2 (1 > 0) and gets more candies (1 > 1 is false, but the rule is "higher rating gets *more*", not strictly more than *all* neighbors with higher ratings). Child 3 has a higher rating than Child 2 (2 > 0) and gets more candies (2 > 1). The minimum is 5 candies.

Example 2:

Input: [1, 2, 2]
Output: 4
Explanation: You can give the first child 1 candy, the second child 2 candies, and the third child 1 candy.
- Child 1 (rating 1) gets 1 candy.
- Child 2 (rating 2) gets 2 candies.
- Child 3 (rating 2) gets 1 candy.
Child 2 has a higher rating than Child 1 (2 > 1) and gets more candies (2 > 1). Child 2 also has a higher rating than Child 3 (2 > 2 is false, so the condition doesn't apply in this direction). The minimum is 4 candies.

Example 3:

Input: [1, 3, 2, 1]
Output: 7
Explanation:
- Child 1 (rating 1): 1 candy
- Child 2 (rating 3): 3 candies (higher rating than Child 1 and Child 3)
- Child 3 (rating 2): 2 candies (higher rating than Child 4)
- Child 4 (rating 1): 1 candy
Total: 1 + 3 + 2 + 1 = 7

Constraints

• 1 <= N <= 2 * 10^4 (where N is the number of children)
• 0 <= ratings[i] <= 2 * 10^4
• The input is a list of integers representing ratings.
• The solution should aim for an efficient time complexity, ideally O(N).

Notes

Consider how to handle children who have the same rating as their neighbors. The rule states "children with a higher rating get more candies than their neighbors." This implies that if two neighbors have the same rating, there's no strict requirement for one to have more candies than the other based solely on rating.

A good approach might involve iterating through the children and their neighbors to establish candy counts, potentially in multiple passes, to ensure all conditions are met simultaneously.