135. Candy
Children stand in a line, and child i has a score ratings[i]. You are handing out candies under two rules:
- every child gets at least one candy;
- a child whose score is strictly higher than an immediate neighbor's must receive more candies than that neighbor.
Neighbors with equal scores carry no obligation either way — the second child in [1, 2, 2] needs more than the first, but the third can drop back to a single candy.
Your function receives the array ratings and returns the minimum total number of candies that satisfies both rules.
Example 1:
Input: ratings = [1, 0, 2]
Output: 5
Explanation: Give 2, 1, 2. The middle child has the lowest score, so both neighbors must beat her single candy — 5 total is the least possible.
Example 2:
Input: ratings = [1, 2, 2]
Output: 4
Explanation: Give 1, 2, 1. The second child outranks the first and gets more; the last two are tied, so the third child can fall back to one candy.
Constraints:
- 1 ≤ ratings.length ≤ 2 * 10⁴
- 0 ≤ ratings[i] ≤ 2 * 10⁴
Hints:
Handing out candies greedily left to right and bumping only when the score rises misses the other direction: in [3, 2, 1] the first child must tower over a whole descending run that only becomes visible later.
Split the constraint in two. A left-to-right pass enforces "higher than my left neighbor ⇒ more than them" (count[i] = count[i-1] + 1 on a rise, else 1). A right-to-left pass enforces the mirror rule; taking max(current, count[i+1] + 1) on a fall preserves the first pass's guarantees. Sum the array.
For O(1) extra space, think in slopes: walking the array you are always on an ascent, a descent, or a plateau. An ascent of length u contributes 2 + 3 + …; a descent of length d contributes 1 + 2 + … below its peak — and only when the descent grows longer than the ascent that preceded it does the peak itself need one extra candy. Track just those run lengths.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: ratings = [1, 0, 2]
Expected output: 5