楼主:
JIWP (JIWP)
2025-06-03 22:16:26来发每日文赚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
}