135. Candy

LeetCode 135. Candy

Description

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

Tags

Greedy

Solution

Solution1:

We create an array, whose length is equal to ratings and all elements are initialized with 1, to store candies each child obtains. We first scan ratings from left, and if the right child has higher rating than that of the left child, we assign the number of candies owned by left child plus 1 to that of the right child. Then we perform the second scan from right. If the left child has higher rating than that of the right child, and candies the left child owns is not more than that of the right child, we assign the number of candies owned by right child plus 1 to that of the left child. Finally, we return the sum of candies array.

Solution 2:

分发糖果总是从1开始并且增量为1。前后相邻两个孩子的评分相等或递增时如图，如果是递减的情况则需要看递减序列长度是多少（从开始下降的那个元素算起，不算上局部最大的元素），并且递减序列的最后一个孩子得到糖果数为1，则根据求和公式可以得到这段递减序列的糖果总数。

但还有一种情况是递减序列长度要大于等于之前的峰值，这时分发糖果数就要补充【递减序列长度-峰值+1】。

Complexity

Solution1:

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Solution 2:

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

Solution1:

func candy(ratings []int) int {
	var ans int
	candies := make([]int, len(ratings))
	for i := range candies {
		candies[i] = 1
	}

	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] = max(candies[i], candies[i+1]+1)
		}
	}

	for _, c := range candies {
		ans += c
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Solution 2:

func candy(ratings []int) int {
	ans, pre, decNum := 1, 1, 0
	for i := 1; i < len(ratings); i++ {
		if ratings[i] >= ratings[i-1] {
			if decNum > 0 {
				ans += decNum * (decNum + 1) / 2
				if pre <= decNum {
					ans += decNum - pre + 1
				}
				pre, decNum = 1, 0
			}
			if ratings[i] == ratings[i-1] {
				pre = 1
			} else {
				pre++
			}
			ans += pre
		} else {
			decNum++
		}
	}
	if decNum > 0 {
		ans += decNum * (decNum + 1) / 2
		if pre <= decNum {
			ans += decNum - pre + 1
		}
	}
	return ans
}

Reference

1. LeetCode 101

2. 分发糖果