135. Candy

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.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

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

Problem Summary

The teacher wants to distribute candies to the children. There are N children standing in a straight line, and the teacher has pre-assigned a rating to each child based on their performance. You need to help the teacher distribute candies to these children according to the following requirements:

• Each child must be allocated at least 1 candy.
• A child with a higher rating must receive more candies than the adjacent children on both sides.

So, under these conditions, what is the minimum number of candies the teacher needs to prepare?

Solution Approach

• The breakthrough for this problem lies in the statement: a child with a higher rating must receive more candies than the adjacent children on both sides. This rule can be understood as two rules. Imagine lining up by height: standing at index 0 and "looking" backward, a higher rating means taller, so the child should receive more candies than the shorter (lower-rated) child in front; standing at index n - 1 and "looking" backward, a higher rating also means taller, and the child should likewise receive more candies than the shorter (lower-rated) child in front. You might wonder: since the rules are the same, why is there a minimum number of candies needed? Because there may be students with the same rating. Scan the array twice to determine, for each student, the minimum number of candies they need to receive to satisfy either the left rule or the right rule. The final number of candies each person receives is the maximum of these two numbers. After the two traversals, add up all the candies to get the minimum number of candies that need to be prepared. Since each person must receive at least 1 candy, add one more to each person's candy count.

Code

package leetcode

func candy(ratings []int) int {
	candies := make([]int, len(ratings))
	for i := 1; i < len(ratings); i++ {
		if ratings[i] > ratings[i-1] {
			candies[i] += candies[i-1] + 1
		}
	}
	for i := len(ratings) - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] && candies[i] <= candies[i+1] {
			candies[i] = candies[i+1] + 1
		}
	}
	total := 0
	for _, candy := range candies {
		total += candy + 1
	}
	return total
}