Candy

Problem

A row of children each has a rating, given as an integer array ratings. You must hand out candies subject to two rules: every child gets at least one candy, and any child with a strictly higher rating than an immediate neighbour must receive more candies than that neighbour. Return the minimum total number of candies you must distribute.

• Between 1 and 100,000 children.
• Ratings are non-negative integers no larger than 1,000,000.
• Children with equal ratings have no constraint between them.

Examples

• ratings = [4, 6, 3] → 4. Give 1, 2, 1: the middle child outranks both neighbours and needs one more than each of them.
• ratings = [7, 7, 9] → 4. Give 1, 1, 2: the first two children tie, so neither needs more than the other.
• ratings = [3, 8, 6, 6, 2] → 7. Give 1, 2, 1, 2, 1; the plateau of 6s lets the count drop back to 1 in the middle.

Hints

1. The constraint has a left side and a right side. What if you only enforced "higher than the left neighbour means more candy" for now?
2. A single left-to-right pass fixes rising slopes. What breaks on falling slopes, and could a second pass in the other direction fix it without undoing the first?
3. Two passes: left-to-right sets c[i] = c[i - 1] + 1 on rises; right-to-left sets c[i] = max(c[i], c[i + 1] + 1) on falls. The max is what keeps both constraints satisfied.