來發每日文賺p幣了，不然抽卡文沒錢可以發
135. Candy
題目 ：
有n個小孩，每個小孩都有各自的rating value
要依照以下的規則發糖果給這些小孩
(1) 每個小孩至少要拿到一顆糖果
(2) 有較高rating value的小孩拿到的糖果個數必須比他鄰近的小孩多
請回傳最少要發幾顆糖果
思路 :
假設 i~i+n的ratings value為嚴格遞減
當遇到這樣的subarray，我們只需要考慮第i個小孩要拿幾顆糖果
i+1 ~ i+n 個小孩就依序給他們 n、n-1、n-2、....2、1顆糖果就好
第i個小孩拿幾顆糖果是由第i-1個小孩決定的
有兩種情況 :
(1) ratings[i] == ratings[i-1]
這種情況第i個小孩拿的糖果數量不用比第i-1個小孩多，所以給他n+1個糖果就好
(2) ratings[i] > ratings[i-1]
這種情況第i個小孩要拿比第i-1個小孩多，最少的情況就是讓他比第i-1個小孩多一顆糖果
就這樣一直找嚴格遞減subarray，然後照上面的規則給糖果就好
golang :
func candy(ratings []int) int {
n := len(ratings)
cnt, ans, prevIdx, lastCnt := 1, 0, 0, 0
var fuck func(int)
fuck = func(i int) {
if prevIdx != 0 && ratings[prevIdx-1] != ratings[prevIdx] && cnt <= lastCnt
{
cnt = lastCnt + 1
}
ans += cnt
lastCnt = cnt
prevIdx++
if prevIdx <= i {
cnt = 1
lastCnt = 1
for prevIdx <= i {
ans += cnt
prevIdx++
cnt++
}
}
}
for i := 0; i < n-1; i++ {
if ratings[i] > ratings[i+1] {
cnt++
} else {
fuck(i)
cnt = 1
prevIdx = i + 1
}
}
fuck(n - 1)
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748960188.A.349.html