小多米已經快到了能吃糖果的年紀了。周末,小多米和小區的小朋友們玩石頭剪刀布遊戲,規定:誰赢的次數多,誰的得分就高,然後按照評分來個小多米和其他小朋友分糖果,并且保證每個小朋友都至少得到一顆糖果(不給就随時哭給你看,手動狗頭)。小多米需要統計出最少需要準備多少顆糖果?
為了幫助小多米解決這個問題,今天我們就來看看算法領域的“分糖果”問題。
“分糖果”問題規則如下:
- 有 N 個小孩站成一列。每個小孩有一個評級。給定數組 ratings 代表這些小孩的評級。
- 每個小孩至少得到一顆糖果。
- 評級越高的小孩可以比他相鄰的兩個小孩得到更多的糖果。
小多米需要計算最少要準備多少糖果?
樣例1如下:
給定評級 = [1, 2], 傳回 3.
樣例2如下:
給定評級 = [1, 1, 1], 傳回 3.
樣例3如下:
給定評級 = [1, 2, 2], 傳回 4. ([1,2,1]).
上面就是算法中“分糖果”問題。聰明的你,知道怎麼幫助小多米解決這個問題嗎?