Candy

Children stand in a line with integer ratings. Give each at least one candy. A child with a strictly higher rating than an adjacent child must receive more…

Children stand in a line with integer ratings. Give each at least one candy. A child with a strictly higher rating than an adjacent child must receive more candies than that neighbor. Return the minimum total candies. Equal adjacent ratings impose no extra inequality.

- 1 <= ratings.length <= 10^4 - 0 <= ratings[i] <= 10^5 - The interactive visualizer accepts at most 20 ratings; longer valid coding inputs are execution-only.

Example 1: input ratings = [1, 0, 5]; output 5. Give [2, 1, 2] candies.

Example 2: input ratings = [1, 2, 2]; output 4. Give [1, 2, 1]; equality does not require an increase.

Example 3: input ratings = [1, 3, 2, 1]; output 7. Give [1, 3, 2, 1]; the descent needs a peak correction.

Category: Greedy Algorithms. Topic: greedy. Difficulty: Hard. Patterns: greedy.