输入分数列表,按分数高低分糖果,要求:

  1. 每人至少一颗
  2. 相邻两个人高分比低分要多。同分则无要求

解析:本质是上坡、上坡。先后分别从左往右、从右往左遍历。

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)
Logo

腾讯云面向开发者汇聚海量精品云计算使用和开发经验,营造开放的云计算技术生态圈。

更多推荐