Problem

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example

Given ratings = [1, 2], return 3.

Given ratings = [1, 1, 1], return 3.

Given ratings = [1, 2, 2], return 4. ([1,2,1]).

Solution

2 passes:

• 1st pass from left to right, if ratings[i] > ratings[i - 1], nums[i] = nums[i - 1] + 1
• 2nd pass from right to left, if ratings[i] < ratings[i - 1], nums[i - 1] = Math.max(nums[i - 1], nums[i] + 1)

Sum up all the numbers in nums, plus the ratings.length if nums is initialized to all 0.