python分糖果问题
****按分数了分糖果,要求:每人至少一颗相邻两个人高分比低分要多。同分则无要求解析:本质是上坡、上坡。先后分别从左往右、从右往左遍历。****class Solution:def candy(self, arr: List[int]) -> int:# write code herenum = len(arr)if num == 1:return 1can = [1]*num
·
输入分数列表,按分数高低分糖果,要求:
- 每人至少一颗
- 相邻两个人高分比低分要多。同分则无要求
解析:本质是上坡、上坡。先后分别从左往右、从右往左遍历。
class Solution:
def candy(self, arr: List[int]) -> int:
# write code here
num = len(arr)
if num == 1:
return 1
can = [1]*num
for i in range(1,num): #上坡,
if arr[i] > arr[i-1]:
can[i] = can[i-1] + 1
for j in range(-2,-num-1,-1): #下坡
if arr[j] > arr[j+1]:
can[j] = max(can[j], can[j+1] + 1) #同时满足上下坡
return sum(can)
更多推荐
所有评论(0)