135. 分发糖果 [hard]

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

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

每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

通过次数23,059 | 提交次数52,707

Second Try

2020-06-24

又是参考题解的版本，来两轮循环，每次只考虑比左边大的部分，或者只考虑比右边大的部分，每次操作只+1，减少了非常痛苦的-1导致负数的考虑。

思路非常清晰，代码非常简单，哎，自己就是没想到。

题解里面还有一个也是上山下山的操作，但是为什么每次下坡最后都能到1我也是没看懂，浪费了两个番茄种，放弃了，f**k. 还是先做自己能理解的版本吧。不然这时间说不过去了。

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int

        两次循环，第一次只考虑比左边大的部分，+1；第二次只考虑比右边大的部分+1；两者取最大值。
        对于任何一个元素，这么一轮下来，比左边大或小，比右边大或小的情况都被考虑到了。
        因为每个操作都是+1，因此不会出现减1一直到负数的情况，之前爬山思路最难的就是负数的情况。思路直接变得很简单。
        而且看起来等号根本不用去考虑。
        """
        cds = [1 for i in ratings]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                cds[i] = cds[i - 1] + 1
        for i in range(len(ratings)-2, -1, -1):  # 这个range的降序写法不注意很容易出错
            if ratings[i] > ratings[i + 1]:
                cds[i] = max(cds[i], cds[i + 1] + 1)
        return sum(cds)

执行用时：48 ms, 在所有 Python 提交中击败了68.53%的用户
内存消耗：14.8 MB, 在所有 Python 提交中击败了50.00%

First Try (Time Exceeded Version)

2020-06-23

按照上坡下坡的思路写的，最严重的问题就是遇到等号的情况，处理了一堆特殊情况，贡献了三四次失败提交。结果改到最后竟然超时了，可怕。

# 超时版本
class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
       
        考虑波峰波谷走法，一路走大则向上走，一路走小则向下走，问题仅仅在于向下走的时候如果到了1了该如何处理，毕竟会影响到前面的连串？
        可以考虑从波峰到波谷的部分抬高一度，波峰前面的就不需要考虑了。

        自己写了个不错的测试案例，在提交前测试了几个bug: 案例[1,0,3,2,2,2,1]

        靠，还是有不能通过的： [29,51,87,87,72,12]， 修改reversed(downloads)搞定
        tmd还是有错误的 [1,2,87,87,87,2,1]， 原因是87的时候是3，第二个87的时候需要直接跳为1，而不是减1为2，这个规则太坑了
        f**k,怎么还有错误的 [1,3,4,5,2]，当i < i-1的时候，i直接为1，而不是cd[i-1]-1,跳悬崖而不是跳台阶
        wtf，还有错误 [0,1,2,3,2,1]，由于跳悬崖的存在，并不是downwards中的每一个都需要提高, 因此还需要及时中断
        tmd的，最后超出时间限制了，f**k,一个一次递减的两万多个元素的数组，波峰波谷法走到尽头了
        """
        cd = [1 for i in ratings]
        downwards = []
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                cd[i] = cd[i-1] + 1
                downwards = []  # empty downwards
            elif ratings[i] <= ratings[i-1]:  # 相等的情况下，选择降1会导致无端多了一个台阶，所有都更高了, 但是要考虑如何处理就麻烦了
                downwards.append(i-1)  # include the previous point, that means peak will be included
                if ratings[i] == ratings[i-1]:  # 这个在前面，也是一个比较tricky的点
                    # print(i, cd, downwards)
                    cd[i] = 1 # 直接重置为1再说（其实默认就是1，不需要写这一步），不管当前的cd[i-1]有多大。
                    continue  # remain 1 for cd[i]
                if cd[i-1] == 1:  # should be larger than or equal to 2 
                    for j in reversed(downwards): # 需要reversed才能够在计算cd[j]的时候，cd[j+1]的数值已经确定
                        # j + 1 should be exists, because i is still not in downwards
                        # 评分相同的考虑：在可以降低台阶的时候，尽管降低；在需要提高台阶的时候，尽量保持平稳不提高
                        if ratings[j] == ratings[j + 1]:  
                            continue
                        # cd[j] += 1则会出现bug，由于相等的存在，导致可能中间出现2的跳跃， 案例[1,0,3,2,2,2,1]
                        # 另外由于跳悬崖的存在，并不是downwards中的每一个都需要提高, 因此还需要及时中断，真是太多坑了
                        if cd[j+1] + 1 < cd[j]:
                            break
                        cd[j] = cd[j+1] + 1
                # cd[i] = cd[i-1] - 1  # might less than 1
                cd[i] = 1 # 太狠了，直接跳为1，而不是一个台阶一个台阶往下走
            # print(i, cd, downwards)
        # print(cd, downwards)
        return sum(cd)

135. 分发糖果 [hard]​

Second Try​

First Try (Time Exceeded Version)​

135. 分发糖果 [hard]

Second Try

First Try (Time Exceeded Version)