题解 | #分糖果问题#

class Solution:  
    def value(self, p: int, List_c: List, List: List): #给定当前孩子位置，目前孩子们得糖情况的数组和题目给的孩子得分的数组
        if List_c[p] != 0:
            if List_c[p + 2] != 0:
                if List[p - 1] == List[p]:
                    List_c[p + 1] = List_c[p + 2] + 1
                else:

                    List_c[p + 1] = max(List_c[p], List_c[p + 2]) + 1
            else:
                if List[p - 1] == List[p]:
                    List_c[p + 1] = 1
                else:
                    List_c[p + 1] = List_c[p] + 1
        else:
            if List_c[p + 2] != 0:
                List_c[p + 1] = List_c[p + 2] + 1
            else:
                List_c[p + 1] = 1

    def candy(self, arr: List[int]) -> int:
        # write code here
        if arr == []:
            return 0
        n = len(arr)
        List_c = []
        ind = sorted(range(len(arr)), key=lambda k: arr[k])  # 用索引按分数升序发糖
        for _ in range(n + 2):
            List_c.append(0)
        for i in range(n):
            self.value(ind[i], List_c, arr)
        return sum(List_c)

p:当前准备被发糖的孩子序号， LIST_C:糖果数组， ARR：孩子得分数组 
 
思路： 从最低分的孩子开始发一颗糖，按得分升序发，那么任何时候没发到糖的肯定不比当前正在发的的分低，有发到糖的肯定不会比当前
正在发的分高。每个人只发一颗糖，直到要发的人旁边的已经有糖开始分类讨论，只需要考虑左右的孩子的分数和发糖情况。
  
旁边孩子同分情况：左边孩子如果发了糖果且与当前孩子得分一样，那他必然是上一个被发糖的人也就是 if List[p - 1] == List[p]:，
所以能发现并且忽略他，因为旁边的分一样高该孩子发几颗都无所谓。事实上分数由低到高排序的时候，同分的从左边开始遍历，也就是说
同分的情况下，左边的孩子发了才发当前孩子，而右边的孩子还没有被发。也就是说只有可能左边出现同分且有糖的情况。所以只需要在
左边有糖同分的情况讨论右边孩子有没有被发糖即可。比如左边孩子5分，当前孩子5分，右边孩子4分，则当前只有当前孩子还没有糖，发比
右边孩子多一颗糖即可。比如左边孩子5分，当前孩子5分，右边孩子6分，则左边孩子已经发糖，右边孩子高于当前孩子的分数还没发到，
当前孩子只发一颗就行。

如果左边孩子和当前孩子不同分：
如果一侧的孩子发了糖，另一侧没有发，则当前孩子发比已经发的邻居多一颗
如果两边都发糖，现在那个孩子发的必须比邻居里糖多的还多一颗因为他的得分更高。  
如果两边的孩子都没有糖，当前孩子一颗即可。

代码实现：创建数组LIST_C来记录目前的孩子们的发糖情况。初始化为全0都没有糖，并且设左右边界各多一个0以便处理边界情况，
因为旁边的孩子还没发到和没有孩子在旁边对于当前孩子的派发而言没区别。发糖就更新该位置。例如：【0，0，1，2，3，1，0】
首尾的0是边界，代表有五个孩子，目前只有排头的孩子还没有发到糖。
接下来用索引按得分升序更新LIST_C就能实现分糖了。