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. 基本思路是:

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

2. 分析:

• 對(duì)于每個(gè)節(jié)點(diǎn), 都要遍歷2遍 因此時(shí)間復(fù)雜度為O(n), 空間復(fù)雜度為O(n)

3. 復(fù)雜度

• 時(shí)間復(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: 曲線法

1. 過(guò)程

• 增加up, down, peak， 從左到右只遍歷1次
• up表示當(dāng)前ratings連續(xù)上升的步數(shù), down表示當(dāng)前ratings連續(xù)下降的步數(shù), peak表示最近的1次連續(xù)上升階段的步數(shù)
• 關(guān)于發(fā)糖的問(wèn)題，可以換個(gè)角度來(lái)看待，即如果將ratings值隨下標(biāo)的變化，看做一個(gè)曲線的話，這個(gè)曲線可以看成是若干個(gè)連續(xù)上升的上坡、若干個(gè)平坡、若干個(gè)下坡構(gòu)成；
• 當(dāng)處于上坡階段時(shí)，我們給第一步的小孩先發(fā)1顆糖， 輪到給第二個(gè)小朋友發(fā)的時(shí)候，就不能只發(fā)1顆糖了，因?yàn)樗鹊谝粋€(gè)小朋友rating高, 所以給他發(fā)2顆糖，依次類推，給第up個(gè)小朋友，就發(fā)up顆糖, 順便更新下peak，表示連續(xù)up的步數(shù)
• 當(dāng)處于平坡的時(shí)候，意味著只需要給小孩發(fā)1顆糖就好了，因?yàn)樗麤](méi)有超過(guò)他左邊鄰居的rating值嘛, 另外peak也重置為1
• 當(dāng)處于下坡的時(shí)候，此時(shí)第一個(gè)處于下坡的小孩，要發(fā)的糖數(shù)要分情況對(duì)待，
  • 當(dāng)down < peak時(shí)，即當(dāng)前是從一個(gè)峰值直接轉(zhuǎn)而下跌，則只需要給這個(gè)小孩發(fā)1顆糖,同時(shí)遞增down；同理，當(dāng)遇到下坡第2個(gè)小孩的時(shí)候，給他發(fā)1顆糖的同時(shí)，要給第1個(gè)小孩再補(bǔ)一顆糖，這一步要發(fā)出去2顆糖；遇到下坡第3個(gè)小孩的時(shí)候，給他發(fā)1顆糖的同時(shí)，要給前2個(gè)小孩各多發(fā)1顆糖，這次發(fā)出去3顆糖；可以看出在下坡第down步的時(shí)候，發(fā)出去down顆糖
  • 當(dāng)down >= peak時(shí), 表示當(dāng)前已經(jīng)下坡太多步了，此時(shí)下坡處第1個(gè)小孩的數(shù)量，已經(jīng)趕上了峰值處小孩的糖數(shù)量，為了保持峰值小孩的糖數(shù)量處于優(yōu)勢(shì)，從當(dāng)前到以后每下坡1步，都要額外給峰值小孩補(bǔ)1顆糖，所以每步發(fā)出去down + 1顆糖
• 將匯總的發(fā)糖數(shù)candies返回即可

2. 分析
   利用此法, 在兩個(gè)指針start和end的幫助下，每個(gè)節(jié)點(diǎn)只被遍歷1次，就得出了結(jié)論，時(shí)間復(fù)雜度降低到了O(n), 空間復(fù)雜度仍然是O(1)
3. 時(shí)間復(fù)雜度 O(n)
4. 空間復(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