【贪心算法】力扣135：分发糖果

本文主要是介绍【贪心算法】力扣135：分发糖果，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。
  请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例1：

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

示例2：

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

思路1：两次遍历

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        num = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                num[i] = num[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                num[i] = max(num[i], num[i + 1] + 1)
        return sum(num)

时间复杂度：O(n)，其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度：O(n)，其中 n 是孩子的数量。我们需要保存所有的左规则对应的糖果数量。

思路2：常数空间+一次遍历（还没懂）
此解法思路和官方题解一致，此部分讲解主要面向未能完全理解官方题解的那部分人，试图从不同切入点来帮助理解这一算法。故变量命名与官方题解保持一致。
算法思路
为叙述方便，暂且引入*numCandy，但最终代码中无需此数组。
正序遍历 *ratings时，即i++循环，考虑*ratings数列的子数列，无非是3种情况：
升序数列，ratings[i] > ratings[i - 1]：
此时暂且令 numCandy[i] = numCandy[i - 1] + 1 即可。
我们可用变量 pre 记录当前循环的numCandy[i]，并实时累加 ans += pre ，同时在下一次循环中 pre = pre + 1 ，这样即可实现空间优化。
后续处理降序数列时，会对升序数列的末尾元素进行再处理，下文将详解，此处只引入变量inc记录升序数列的长度。
相邻元素相等，ratings[i] == ratings[i - 1]：
此时 numCandy[i] = 1 即 pre = 1 即可。
降序数列，ratings[i] < ratings[i - 1]：
此时效仿升序数列的处理思路，令 numCandy[i - 1] = numCandy[i] + 1 ，但这样将需要倒序遍历，思维难点出现。
我们可换一种思路看待降序数列：
降序数列中每增加 1 个元素，新元素的 numCandy 值为 1 ，之前元素的 numCandy 值均 +1 ，例如：
原数列：ratings = [9, 8, 7]; numCandy = [3, 2, 1];
新数列：ratings = [9, 8, 7, 6]; numCandy = [4, 3, 2, 1];
此时，*numCandy总和的变化量 delta_numCandy = 4 + 3 + 2 + 1 - 3 - 2 - 1 = 4
可以发现，delta_numCandy 等于当前降序数列的长度。此结论可进行形式化地证明，但篇幅所限，本文略去。
故，可使用变量 dec 记录当前降序数列的长度，降序数列中每新增一个元素，执行一次 ans += dec 。
需要注意的是:
降序数列刚刚产生时，无需考虑前方最近升序数列。即，dec < inc 时，无需将前方最近升序数列的尾部元素纳入当前降序数列中。例如：
ratings = [3, 4, 9, 8]; numCandy = [1, 2, 3, 1];满足题意。
解释： 虽然 sub_ratings = [9, 8] 构成一个降序数列，但我们无需更新元素[9]的 numCandy 值，只需要将元素[8]的 numCandy 值设为 1 。
当前降序数列的长度大于等于前方最近升序数列长度时，需要前方最近升序数列的末尾元素纳入当前降序数列中一并处理，例如：
原数列：ratings = [3, 4, 9, 8, 7]; numCandy = [1, 2, 3, 2, 1]; dec = 2;
新数列：ratings = [3, 4, 9, 8, 7, 6]; numCandy = [1, 2, 4, 3, 2, 1]; dec = 4;
元素[9]的 numCandy 值更新为4。此时经历的操作为：
将元素[6]纳入降序数列，dec = 3
将元素[9]纳入降序数列，dec = 4

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

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

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-leetcode-solution-f01p/

时间复杂度：O(n)，其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

这篇关于【贪心算法】力扣135：分发糖果的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！