135. 分发糖果 - 力扣（LeetCode）

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

标准的解法是前后两次遍历取最大，但这样会消耗O(n)O(n)的空间，这里给出一次遍历贪心算法的实现.

思路:
首先只考虑ratings不减的情况：若ratings[i]等于ratings[i-1]，此时糖果数可直接从11重新开始；若ratings[i]>>ratings[i-1]，只需分发比上一位多一个糖果即可。这部分我们只需要一个变量pre维护上一位的糖果数

1
2
3
4
5
6
7
8
int candy = 1, pre = 1;
    for (int i = 1; i < ratings.size(); i++) {
        int gap = ratings[i] - ratings[i-1];
        if (gap == 0) pre = 1;
        else pre += 1;
        candy += pre;
    }
return candy;

接下来考虑ratings的递减部分：例如ratings[i-1] = 3,ratings[1] = 2，当pre = 3时，我们只考虑现有的，增加第i+1i+1个小朋友时，最优解即是只给他一个糖果。接下来，若下一位ratings仍递减，那么我们也只给新的小朋友一个糖果，不过，我们还需要为前一个小朋友再增加一个糖果。但是，如果下一位仍是递减，我们就需要增加44个糖果了，因为最开始的33个糖果的小朋友和他右边评分更低的小朋友糖果数一样，我们需要再为他分配一个糖果。

我们需要一个变量peak记录递减序列的头，即第一个小朋友的糖果数，对于剩下的小朋友，我们只需倒着发放，最后一位一个，倒数第二位两个,…\dots,直到第二个小朋友，然后再修正第一个小朋友的糖果数，使其高于第二个小朋友。

我们从遍历的角度去实现：再用一个变量de记录递减序列的长度，当新增的ratings小于前一位，我们总共需要额外de个糖果（递减序列除第一个外+新的小朋友 每人一个）。特别地，当de≥\geqpeak时，第二位的糖果数将追上第一位，这时我们每次需要de+1个糖果（补偿）

及时更新de，在递减序列结束时重置de，同时更新pre（必为11）。这里，我们可以省去peak变量，直接用pre来代替，在递减序列中不再更新pre，让它充当peak，而在出递减序列后再重新将其重置为11。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int candy(vector<int>& ratings) {
    int candy = 1, pre = 1, de = 1;
    for (int i = 1; i < ratings.size(); i++) {
        int gap = ratings[i] - ratings[i-1];
        if (gap < 0) {
            if (de >= pre) candy += 1; //补偿
            candy += de;
            de++;
            continue;
        }
        if (de != 1) { //出递减序列 重置
            pre = 1;
            de = 1;
        }
        if (gap == 0) pre = 1;
        else pre += 1;
        candy += pre;
    }
    return candy;
}

时间复杂度:O(n)O(n)，空间复杂度:O(1)O(1).