noodleProblems/
Candy
#159

Candy

AlgorithmhardArrayGreedy

n children stand in a line. Each child has a rating given by ratings[i]. You must hand out candies to every child so that:

- Every child receives at least one candy. - Any child whose rating is strictly greater than an immediate neighbor's rating must receive strictly more candies than that neighbor.

Return the minimum total number of candies you need to satisfy both rules.

Example cases

  • single dip
    in ratings = [1,0,2]
    out 5
    Child 1 has the lowest rating and gets 1 candy. Both neighbors rate higher than child 1, so each needs at least 2. Total: 2 + 1 + 2 = 5.
  • plateau after a rise
    in ratings = [1,2,2]
    out 4
    Child 1 rates higher than child 0, so child 1 gets 2 and child 0 gets 1. Child 2 ties child 1, so no ordering is required between them and child 2 gets 1. Total: 1 + 2 + 1 = 4.
  • strictly increasing
    in ratings = [1,2,3,4]
    out 10
    Each child rates higher than the last, so the candies climb 1, 2, 3, 4 for a total of 10.
  • single child
    in ratings = [5]
    out 1
    One child always gets exactly 1 candy.

Constraints

  • n == ratings.length
  • 1 <= n <= 2 * 10^4
  • 0 <= ratings[i] <= 2 * 10^4
Saved
ratings =
[1,0,2]