1. 题目描述

n?个孩子站成一排。给你一个整数数组?ratings?表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到?1?个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的?最少糖果数目?。

示例?1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例?2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

n == ratings.length
1 <= n <= 2 * 10^4
0 <= ratings[i] <= 2 * 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/candy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

2.1 思路

? ? ? ? 显而易见的是，对于每个评分值为局部极小值（local minima）的小朋友，都只给一个糖果。

? ? ? ? 然后从所有局部评分极小值出发向两边搜索，分别给位于两侧的小朋友分配糖果，直到两侧的极大值点。

? ? ? ? 对于局部评分极大值点，从它的两侧的局部极小值点出发所得的糖果分配值可能不一样，比如说分数为[0,1,2,3,4,2,0]，对于索引为4的学生而言，从左侧的0出发他应该得到5课糖果，从右侧的0出发则应该得到3课糖果，这种情况下，取两者中的最大值即可。

? ? ? ? 如果每个人的分数都不相同，（运行效率另说）按照以上规则就可以解决了。

? ? ? ? 但是，当出现连续多个人的分数相同的情况，由于两个分数相同的同学所得糖果没有约束，情况会变得比较复杂。可以分为以下三种情况来讨论（为了描述方便，称连续多个分数相同的构成一个平台区）：

? ? ? ? case1:该平台区处于盆地谷底，即局部极小值区域。这种情况下，大家都分发一个糖果。

? ? ? ? case2:该平台区处于峰顶，即局部极大值区域。这种情况下，两侧的学生分别根据自己那一侧的局部极小点向上搜索所得结果进行糖果分配。平台区域中间的学生分配一个糖果即可。

? ? ? ? case3:该平台区处于上升段半山腰。这种情况下，左端的学生根据左侧的局部极小点向上搜索所得结果进行糖果分配。其余学生分配一个糖果即可。??

? ? ? ? case4:该平台区处于下降段半山腰。这种情况下，右端的学生根据右侧的局部极小点向上搜索所得结果进行糖果分配。其余学生分配一个糖果即可。

? ? ? ? 处于两端的平台区。左端平台区，除了最右侧端点按照上述规则进行判断，其余全部分配一个糖果；右端平台区，除了最左侧端点按照上述规则进行判断，其余全部分配一个糖果。

? ? ? ? 话说。。。这个规则真的是太不公平了^-^.

? ? ? ? 好，如何用代码来实现以上搜索规则呢？

2.2 实现

? ? ? ? 首先遍历ratings，将每个学生标记为以下几类：

固定分一个糖果（平台区中间的学生），标记为-1
极小值点，标记为0
极大值点，标记为1
其它点，标记为2

? ? ? ? 然后，遍历每个极小值点，从每个极小值点出发向两边搜索，直到遇到极大值点或者标记为-1的点或者另一个极小值点为止。每走一步加一颗糖果。（对于极大值点）如果所分配的糖果数小于已分配的糖果数，则保持不变。

3. 代码实现

from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        if len(ratings) == 1:
            return 1
        N = len(ratings)
        flags = N * [0]
        
        for k in range(len(ratings)):
            if k==0:
                if ratings[0] > ratings[1]:
                    flags[0] = 1
                elif ratings[0] == ratings[1]:
                    flags[0] = -1
                else:
                    flags[0] = 0
                continue
            if k==N-1:
                if ratings[N-1] > ratings[N-2]:
                    flags[N-1] = 1
                elif ratings[N-1] == ratings[N-2]:
                    flags[N-1] = -1
                else:
                    flags[N-1] = 0
                continue
            if ratings[k-1]==ratings[k] and ratings[k+1]==ratings[k]:
                flags[k] = -1
            elif ratings[k-1]<ratings[k] and ratings[k+1]<ratings[k]:
                flags[k] = 1
            elif ratings[k-1]>ratings[k] and ratings[k+1]>ratings[k]:
                flags[k] = 0
            elif ratings[k-1]>ratings[k] and ratings[k+1]==ratings[k]:
                flags[k] = 0
            elif ratings[k-1]<ratings[k] and ratings[k+1]==ratings[k]:
                flags[k] = 1
            elif ratings[k-1]==ratings[k] and ratings[k+1]>ratings[k]:
                flags[k] = 0
            elif ratings[k-1]==ratings[k] and ratings[k+1]<ratings[k]:
                flags[k] = 1
            else:
                flags[k] = 2
        # print(flags)
        nums = len(ratings) * [0]
        for k in range(len(ratings)):
            if flags[k] == -1:
                nums[k] = 1
            elif flags[k] == 0:
                nums[k] = 1
                # backward search
                j = k-1
                while j>=0:
                    # print(j,flags[j])
                    if flags[j]==-1 or flags[j]==0:
                        break
                    elif flags[j]!=1:
                        nums[j] = nums[j+1]+1
                        j = j-1
                    else:
                        nums[j] = nums[j+1]+1 if nums[j+1]+1>nums[j] else nums[j]
                        break
                # forward search
                j = k+1
                while j<N:
                    if flags[j]==-1 or flags[j]==0:
                        break
                    elif flags[j]!=1:
                        nums[j] = nums[j-1]+1
                        j = j+1
                    else:
                        nums[j] = nums[j-1]+1 if nums[j-1]+1>nums[j] else nums[j]
                        break
                # print(k,nums)
        # print(nums)
        return sum(nums)
    
if __name__ == "__main__":
    
    sln = Solution()    
    
    ratings = [0]
    print(sln.candy(ratings))

    ratings = [1,0]
    print(sln.candy(ratings))

    # ratings = [1,0,2]
    # print(sln.candy(ratings))
    
    # ratings = [1,2,2]
    # print(sln.candy(ratings))
    
    # ratings = [1,2,2,2,2,2,3,2,2,2]
    # print(sln.candy(ratings))
    
    # ratings = [1,2,3,4,5,4,3,2,1,1]
    # print(sln.candy(ratings))
    
    ratings = [1,2,3,5,4,3,2,1,4,3,2,1,3,2,1,1,2,3,4]
    print(sln.candy(ratings))

????????执行用时：112 ms, 在所有?Python3?提交中击败了6.00%的用户

????????内存消耗：17.1 MB, 在所有?Python3?提交中击败了28.34%的用户

? ? ? ? 虽然实现得很冗长，而且性能也很拉胯，但是毕竟是自己手撕的difficult级别的题目，还是得鼓励一下自己。

????????

????????官解摘录如下（其实思路是相近的，只是我的实现手法太差），留待慢慢消化：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [0] * n
        for i in range(n):
            if i > 0 and ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
            else:
                left[i] = 1
        
        right = ret = 0
        for i in range(n - 1, -1, -1):
            if i < n - 1 and ratings[i] > ratings[i + 1]:
                right += 1
            else:
                right = 1
            ret += max(left[i], right)
        
        return ret

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-leetcode-solution-f01p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

????????官解还给出了“方法二：常数空间遍历”，不过说明起来比较长，暂且免了。

? ? ? ? 回到总目录：笨牛慢耕的Leetcode每日一题总目录(动态更新。。。)