算法题--给小朋友发糖问题

image.png

0. 链接

题目链接

1. 题目

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:

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:

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.

2. 思路1: 双向加成法

1. 基本思路是:

• 首先初始化一个candies数组, 表示每个小孩分到的糖数, 初始为1
• 先自i=1开始从左到右遍历ratings数组, 当遇到ratings[i] > ratings[i - 1]，即遇到一个分数比左边邻居高的小朋友时, 则 将他的糖数变为max(candies[i], candies[i - 1] + 1), 确保他的糖比左边小朋友多
• 再从i = n - 2开始从右到左遍历ratings数组, 当遇到ratings[i] > ratings[i + 1]时, 即遇到一个分数比右边邻居高的小朋友时, 则将他的糖数变为max(candies[i], candies[i + 1] + 1), 确保他的糖同时也比右边的邻居多

2. 分析:

• 对于每个节点, 都要遍历2遍 因此时间复杂度为O(n), 空间复杂度为O(n)

3. 复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(n)

3. 代码

# coding:utf8
from typing import List


class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n == 0:
            return 0

        candies = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                new_num = max(candies[i], candies[i - 1] + 1)
                candies[i] = new_num
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                new_num = max(candies[i], candies[i + 1] + 1)
                candies[i] = new_num

        return sum(candies)


def my_test(solution, ratings):
    print('input: ratings={}; output: {}'.format(ratings, solution.candy(ratings)))


solution = Solution()

my_test(solution, [1, 0, 2])
my_test(solution, [1, 2, 2])
my_test(solution, [2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0])

输出结果

input: ratings=[1, 0, 2]; output: 5
input: ratings=[1, 2, 2]; output: 4
input: ratings=[2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0]; output: 21

4. 结果

image.png

5. 思路2: 曲线法

1. 过程

• 增加up, down, peak， 从左到右只遍历1次
• up表示当前ratings连续上升的步数, down表示当前ratings连续下降的步数, peak表示最近的1次连续上升阶段的步数
• 关于发糖的问题，可以换个角度来看待，即如果将ratings值随下标的变化，看做一个曲线的话，这个曲线可以看成是若干个连续上升的上坡、若干个平坡、若干个下坡构成；
• 当处于上坡阶段时，我们给第一步的小孩先发1颗糖， 轮到给第二个小朋友发的时候，就不能只发1颗糖了，因为他比第一个小朋友rating高, 所以给他发2颗糖，依次类推，给第up个小朋友，就发up颗糖, 顺便更新下peak，表示连续up的步数
• 当处于平坡的时候，意味着只需要给小孩发1颗糖就好了，因为他没有超过他左边邻居的rating值嘛, 另外peak也重置为1
• 当处于下坡的时候，此时第一个处于下坡的小孩，要发的糖数要分情况对待，
  • 当down < peak时，即当前是从一个峰值直接转而下跌，则只需要给这个小孩发1颗糖,同时递增down；同理，当遇到下坡第2个小孩的时候，给他发1颗糖的同时，要给第1个小孩再补一颗糖，这一步要发出去2颗糖；遇到下坡第3个小孩的时候，给他发1颗糖的同时，要给前2个小孩各多发1颗糖，这次发出去3颗糖；可以看出在下坡第down步的时候，发出去down颗糖
  • 当down >= peak时, 表示当前已经下坡太多步了，此时下坡处第1个小孩的数量，已经赶上了峰值处小孩的糖数量，为了保持峰值小孩的糖数量处于优势，从当前到以后每下坡1步，都要额外给峰值小孩补1颗糖，所以每步发出去down + 1颗糖
• 将汇总的发糖数candies返回即可

2. 分析
   利用此法, 在两个指针start和end的帮助下，每个节点只被遍历1次，就得出了结论，时间复杂度降低到了O(n), 空间复杂度仍然是O(1)
3. 时间复杂度 O(n)
4. 空间复杂度 O(1)

6. 代码

# coding:utf8
from typing import List


class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n <= 1:
            return n

        up = 1
        peak = up
        down = 0
        candies = 1
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                up += 1
                peak = up
                down = 0
                candies += up
            elif ratings[i] < ratings[i - 1]:
                up = 1
                down += 1
                candies += down if down < peak else down + 1
            else:
                up = 1
                down = 0
                peak = up
                candies += 1

        return candies


def my_test(solution, ratings):
    print('input: ratings={}; output: {}'.format(ratings, solution.candy(ratings)))


solution = Solution()

my_test(solution, [1, 0, 2])
my_test(solution, [1, 2, 2])
my_test(solution, [2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0])

输出结果

input: ratings=[1, 0, 2]; output: 5
input: ratings=[1, 2, 2]; output: 4
input: ratings=[2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0]; output: 21

7. 结果

image.png