Candy

Hard · Greedy · about 25 minutes

Asked at Amazon, Google, Uber.

Children stand in a line with ratings. Give each child at least one candy, and give any child with a higher rating than an adjacent neighbor more candies than that neighbor. Return the minimum total number of candies.