贪心策略、分配问题

题目

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

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

  • 每个孩子至少分配到 1 个糖果。
  • 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例1:

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

示例2：

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

题解

方法一：两次遍历

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理

  • 左规则：当ratings[i-1]<ratings[i]时，i号学生的糖果数量将比i-1号孩子的糖果数量多
  • 右规则：当ratings[i]>ratings[i+1]时，i号学生糖果数比i+1号孩子糖果数量多。

初始化长度为len(ratings)1的列表

  • 先从左至右遍历，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；
  • 再从右至左遍历，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def candy(self, ratings) -> int:
        n=len(ratings)
        
        if n==0:
            return 0
        
        tmp=[1]*n
        for i in range(1,n):
            if ratings[i]>ratings[i-1]:
                tmp[i]=tmp[i-1]+1

        for j in range(n-1,0,-1):
            if ratings[j-1]>ratings[j] and tmp[j-1]<=tmp[j]:
                tmp[j-1]=tmp[j]+1

        sum=0
        for c in tmp:
            sum+=c
        return sum
1
2
3
a=Solution()
ratings=[1,0,2]
a.candy(ratings)
5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def candy(self, ratings) -> 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
1
2
3
a=Solution()
ratings=[1,2,2]
a.candy(ratings)
4

复杂度分析

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

方法二：常数空间遍历

我们从左到右枚举每一个同学，记前一个同学分得的糖果数量为$pre$

  • 如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 $pre+1$ 个糖果即可。

  • 否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。

    • 我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。
    • 同时注意当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中

这样，我们只要记录当前递减序列的长度dec，最近的递增序列的长度 inc 和前一个同学分得的糖果数量pre 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def candy(self, ratings) -> 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
1
2
3
a=Solution()
ratings=[1,3,5,3,2,1]
print(a.candy(ratings))
13

复杂度分析

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

空间复杂度：O(1)。我们只需要常数的空间保存若干变量。


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2021/01/02/LeetCode-D-%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95-135.%20%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C/