算法題--給小朋友發(fā)糖問題

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: 雙向加成法

基本思路是:

首先初始化一個candies數(shù)組, 表示每個小孩分到的糖數(shù), 初始為1
先自i=1開始從左到右遍歷ratings數(shù)組, 當(dāng)遇到ratings[i] > ratings[i - 1]蜈首，即遇到一個分?jǐn)?shù)比左邊鄰居高的小朋友時, 則將他的糖數(shù)變?yōu)?code>max(candies[i], candies[i - 1] + 1), 確保他的糖比左邊小朋友多
再從i = n - 2開始從右到左遍歷ratings數(shù)組, 當(dāng)遇到ratings[i] > ratings[i + 1]時, 即遇到一個分?jǐn)?shù)比右邊鄰居高的小朋友時, 則將他的糖數(shù)變?yōu)?code>max(candies[i], candies[i + 1] + 1), 確保他的糖同時也比右邊的鄰居多

分析:

對于每個節(jié)點, 都要遍歷2遍因此時間復(fù)雜度為O(n), 空間復(fù)雜度為O(n)

復(fù)雜度

時間復(fù)雜度 O(n)
空間復(fù)雜度 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])

輸出結(jié)果

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. 結(jié)果

image.png

5. 思路2: 曲線法

過程

增加up, down, peak赏淌，從左到右只遍歷1次
up表示當(dāng)前ratings連續(xù)上升的步數(shù), down表示當(dāng)前ratings連續(xù)下降的步數(shù), peak表示最近的1次連續(xù)上升階段的步數(shù)
關(guān)于發(fā)糖的問題六水，可以換個角度來看待掷贾，即如果將ratings值隨下標(biāo)的變化想帅，看做一個曲線的話，這個曲線可以看成是若干個連續(xù)上升的上坡旨剥、若干個平坡轨帜、若干個下坡構(gòu)成蚌父；
當(dāng)處于上坡階段時梢什，我們給第一步的小孩先發(fā)1顆糖嗡午，輪到給第二個小朋友發(fā)的時候荔睹，就不能只發(fā)1顆糖了僻他，因為他比第一個小朋友rating高, 所以給他發(fā)2顆糖腊尚，依次類推婿斥，給第up個小朋友民宿，就發(fā)up顆糖, 順便更新下peak活鹰，表示連續(xù)up的步數(shù)
當(dāng)處于平坡的時候志群，意味著只需要給小孩發(fā)1顆糖就好了赖舟，因為他沒有超過他左邊鄰居的rating值嘛, 另外peak也重置為1
當(dāng)處于下坡的時候宾抓，此時第一個處于下坡的小孩，要發(fā)的糖數(shù)要分情況對待紧显，
- 當(dāng)down < peak時缕棵，即當(dāng)前是從一個峰值直接轉(zhuǎn)而下跌招驴，則只需要給這個小孩發(fā)1顆糖,同時遞增down别厘；同理触趴，當(dāng)遇到下坡第2個小孩的時候冗懦，給他發(fā)1顆糖的同時披蕉，要給第1個小孩再補一顆糖没讲，這一步要發(fā)出去2顆糖食零；遇到下坡第3個小孩的時候贰谣，給他發(fā)1顆糖的同時吱抚，要給前2個小孩各多發(fā)1顆糖秘豹，這次發(fā)出去3顆糖；可以看出在下坡第down步的時候涮坐，發(fā)出去down顆糖
- 當(dāng)down >= peak時, 表示當(dāng)前已經(jīng)下坡太多步了，此時下坡處第1個小孩的數(shù)量捷雕，已經(jīng)趕上了峰值處小孩的糖數(shù)量壹甥，為了保持峰值小孩的糖數(shù)量處于優(yōu)勢句柠，從當(dāng)前到以后每下坡1步，都要額外給峰值小孩補1顆糖缸榄，所以每步發(fā)出去down + 1顆糖
將匯總的發(fā)糖數(shù)candies返回即可

分析
利用此法, 在兩個指針start和end的幫助下甚带，每個節(jié)點只被遍歷1次鹰贵，就得出了結(jié)論碉输，時間復(fù)雜度降低到了O(n), 空間復(fù)雜度仍然是O(1)
時間復(fù)雜度 O(n)
空間復(fù)雜度 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])

輸出結(jié)果

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. 結(jié)果

image.png