1. 題目描述
老師想給孩子們分發(fā)糖果，有 N 個(gè)孩子站成了一條直線，老師會(huì)根據(jù)每個(gè)孩子的表現(xiàn)，預(yù)先給他們?cè)u(píng)分。
你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：
每個(gè)孩子至少分配到 1 個(gè)糖果。
相鄰的孩子中，評(píng)分高的孩子必須獲得更多的糖果。
那么這樣下來(lái)，老師至少需要準(zhǔn)備多少顆糖果呢？
示例 1:
輸入: [1,0,2]
輸出: 5
解釋: 你可以分別給這三個(gè)孩子分發(fā) 2、1、2 顆糖果。
示例 2:
輸入: [1,2,2]
輸出: 4
解釋: 你可以分別給這三個(gè)孩子分發(fā) 1、2、1 顆糖果。
第三個(gè)孩子只得到 1 顆糖果，這已滿足上述兩個(gè)條件。
2. 思路
構(gòu)造一個(gè)數(shù)組，記錄每個(gè)孩子的分得的糖果數(shù)，初始化為1。利用動(dòng)態(tài)規(guī)劃，
dp[i] = dp[j] + 1, 當(dāng)ratings[i] > ratings[j],且 i = j-1 或 i= j+1。
- 從左向右遍歷得分?jǐn)?shù)組，保證一個(gè)方向上，得分高的孩子糖果多
-
從右向左遍歷得分?jǐn)?shù)組，保證另一個(gè)方向上，得分高的孩子糖果多。
但是需要注意一點(diǎn)，如果有中間的孩子得分最高，如[1,3,2,2,1]，那么在從左到右便利的過(guò)程中，第二個(gè)孩子（得分為3）獲得糖果會(huì)加上1。從右到左遍歷的過(guò)程中，第二個(gè)孩子（得分為3）獲得糖果還會(huì)加上1，其實(shí)我們發(fā)現(xiàn)第二個(gè)孩子有兩個(gè)糖果就可以滿足條件，因此在第二遍遍歷的時(shí)候，需要加上一個(gè)判斷條件，即當(dāng)前孩子的糖果數(shù)是否已經(jīng)滿足條件了。
2.1 Python代碼：
class
Solution
(
object
)
:
def
candy
(
self
,
ratings
)
:
""" :type ratings: List[int] :rtype: int """
if
ratings
==
None
:
return
0
lenth
=
len
(
ratings
)
dp
=
[
1
for
i
in
range
(
lenth
)
]
sum
=
0
for
i
in
range
(
1
,
len
(
ratings
)
)
:
if
ratings
[
i
]
>
ratings
[
i
-
1
]
:
dp
[
i
]
=
dp
[
i
-
1
]
+
1
for
i
in
range
(
len
(
ratings
)
-
2
,
-
1
,
-
1
)
:
if
ratings
[
i
]
>
ratings
[
i
+
1
]
and
dp
[
i
]
<=
dp
[
i
+
1
]
:
dp
[
i
]
=
dp
[
i
+
1
]
+
1
for
i
in
range
(
lenth
)
:
sum
+=
dp
[
i
]
return
sum
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
