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
顆糖
- 當(dāng)
- 將匯總的發(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