⚔ LeetCode | 135. Candy

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 135. Candy

Difficulty : Hard

There are N children standing in a line. Each child is assigned a rating value.

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 1:

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

Example 2:

1
2
3
4
Input: [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.

Analysis

这道题需要分糖果给小朋友，要求相邻的分数较高的小朋友的糖果数不能少于分数较低的。

根据这个规则，从分数最低的小朋友开始分似乎是比较好的做法，但是存在一个问题：如果同时有两个分数最低的小朋友呢？那就需要取他们所决定的邻居数的最大值了。

Approach 1

最简单的做法就是分别从两边开始分配，然后最后取他们之间的最大值。

具体做法如下：

声明一个数组，用于保存分给该小朋友的糖果数。

给第一个小朋友分最少的糖果，1

从一端向另一端遍历小朋友的分数：

  • 当前分数大于前一个分数，那么需要给这个小朋友更多的糖果，因此至少需要分配多一个糖果
  • 当前分数等于前一个分数，题目并没有要求相等分数需要相等的糖果，因此可以给他分配最少的糖果，1
  • 当前分数小于前一个分数，因为题目要求的最少糖果总数，因此可以给他分配最少的糖果，1

为什么要左右都遍历一次呢？我们来看个例子

假设小朋友的分数为[1, 3, 2, 2, 1]

按照上面的规则，从左到右遍历的结果为[1, 2, 1, 1, 1]，这里就产生问题了，第四个小朋友分数比第五个小朋友高，但是糖果数并没有比他高。

我们再从右边开始遍历一次，得到结果[1, 2, 1, 2, 1]，然后取两个数组的每个元素的最大值，加起来得到的就是一共需要最少的糖果数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func candy(ratings []int) int {
	if len(ratings) == 0 {
		return 0
	}
	left, right := []int{1},[]int{1}
	for i := 1; i < len(ratings); i++ {
		if ratings[i] > ratings[i - 1] {
			left = append(left, left[len(left) - 1] + 1)
		} else {
			left = append(left, 1)
		}
	}
	for i := len(ratings) - 2; i >= 0; i-- {
		if ratings[i] > ratings[i + 1] {
			right = append(right, right[len(right) - 1] + 1)
		} else {
			right = append(right, 1)
		}
	}
	sum := 0
	for i := range left {
		if left[i] > right[len(right) - i - 1] {
			sum += left[i]
		} else {
			sum += right[len(right) - i - 1]
		}
	}
	return sum
}

这个算法需要遍历数组两次，时间复杂度为O(n)，空间复杂度为O(n)

Summary

这道题的主要思想就是贪婪，需要尽可能小的为小朋友分配糖果，只要明白了如何分配可以最小化糖果总数，那么解出这道题也是十分简单的。

土豪通道
0%