分糖果问题

分糖果问题_牛客题霸_牛客网

问题简述

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
    1. 每个孩子不管得分多少，起码分到一个糖果。
    2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组 arr 代表得分数组，请返回最少需要多少糖果。

进阶1：空间复杂度 O(1)
进阶2：相邻分数相同分到的糖果数一样，其他规则不变（阿里）

思路：贪心

分糖果问题及其进阶 - 左程云

• 分别记录从左到右和从右到左的“坡度”序列，然后在各位置去对应坡度的最大值；

• 具体“坡度”的定义如下：

  分数序列：
      arr = [1,2,3,4,2,1,2,3,2]
  左→右坡度，即 l[i] = l[i-1] + 1 if arr[i] > arr[i-1] else 1
      l   = [1,2,3,4,1,1,2,3,1]
  右→左坡度，即 r[i] = r[i+1] + 1 if arr[i] > arr[i+1] else 1
      r   = [1,1,1,3,2,1,1,2,1]
  对应位置取最大值
      ret = [1,2,3,4,2,1,2,3,1] -> 19

• 进阶 1：使用两个变量记录上坡长度和下坡长度（需要一定的编程技巧）；

  分发糖果（方法2） - 力扣官方题解

• 进阶 2：生成 l 和 r 的过程中若当前得分与上一位置相同，则取上一位置的得分即可；

Python

class Solution:
    def candy(self , arr: List[int]) -> int:
        N = len(arr)
        l = [1] * N
        r = [1] * N
        for i in range(1, N):
            l[i] = l[i - 1] + 1 if arr[i] > arr[i - 1] else 1
            r[N - i - 1] = r[N - i] + 1 if arr[N - i - 1] > arr[N - i] else 1
            
        ret = 0
        for i in range(N):
            ret += max(l[i], r[i])
        return ret

Python（进阶 1）

class Solution:
    def candy(self, arr: List[int]) -> int:
        N = len(arr)
        ret = 1
        inc, dec, pre = 1, 0, 1

        for i in range(1, N):
            if arr[i] >= arr[i - 1]:
                dec = 0
                pre = 1 if arr[i] == arr[i - 1] else pre + 1
                ret += pre
                inc = pre
            else:
                dec += 1
                if dec == inc: dec += 1
                ret += dec
                pre = 1

        return ret

Python（进阶 2）

class Solution:
    def candy(self , arr: List[int]) -> int:
        N = len(arr)
        l = [1] * N
        r = [1] * N
        for i in range(1, N):
            if arr[i] > arr[i - 1]: l[i] = l[i - 1] + 1
            elif arr[i] == arr[i - 1]: l[i] = l[i - 1]
            
            if arr[N - i - 1] > arr[N - i]: r[N - i - 1] = r[N - i] + 1
            elif arr[N - i - 1] == arr[N - i]: r[N - i - 1] = r[N - i]
            
        ret = 0
        for i in range(N):
            ret += max(l[i], r[i])
        return ret