vlambda博客
学习文章列表

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

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

• 每个孩子至少分配到1个糖果。

• 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

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

输入：[1,0,2]

输出：5

解释：你可以分别给这三个孩子分发2、1、2颗糖果。

输入：[1,2,2]

输出：4

解释：你可以分别给这三个孩子分发1、2、1颗糖果。

     第三个孩子只得到1颗糖果，这已满足上述两个条件。

这题有3个条件

 1public int candy(int[] ratings) {
 2    int length = ratings.length;
 3    //记录的是从左往右循环的结果
 4    int[] left = new int[length];
 5    //记录的是从右往左循环的结果
 6    int[] right = new int[length];
 7    //因为每个孩子至少有一个糖果，默认都给他们一个
 8    Arrays.fill(left, 1);
 9    Arrays.fill(right, 1);
10    //统计最少的总共糖果数量
11    int total = 0;
12    //先从左往右遍历，如果当前孩子的得分比左边的高，
13    //那么当前孩子的糖果要比左边孩子的多一个
14    for (int i = 1; i < length; i++) {
15        if (ratings[i] > ratings[i - 1])
16            left[i] = left[i - 1] + 1;
17    }
18    //然后再从右往左遍历，如果当前孩子的得分比右边的高，
19    //那么当前孩子的糖果要比右边边孩子的多一个
20    for (int i = length - 1; i > 0; i--) {
21        if (ratings[i - 1] > ratings[i])
22            right[i - 1] = right[i] + 1;
23    }
24    //要满足左右两边的条件，那么当前孩子的糖果就要取
25    //从左往右和从右往左的最大值。
26    for (int i = 0; i < length; i++) {
27        //累计每个孩子的糖果
28        total += Math.max(left[i], right[i]);
29    }
30    return total;
31}

 1public int candy(int[] ratings) {
 2    int length = ratings.length;
 3    int[] count = new int[length];
 4    //默认给每个孩子一个糖果
 5    Arrays.fill(count, 1);
 6    //先从左往右遍历
 7    for (int i = 1; i < length; i++) {
 8        if (ratings[i] > ratings[i - 1])
 9            count[i] = count[i - 1] + 1;
10    }
11    //因为下面的for循环中，total没有统计最后一个孩子的糖果，所以这里total
12    //的默认值就是最后那个孩子的糖果数量
13    int total = count[length - 1];
14    //从右往左遍历，然后顺便累加total的值
15    for (int i = length - 1; i > 0; i--) {
16        if (ratings[i - 1] > ratings[i])
17            count[i - 1] = Math.max(count[i - 1], count[i] + 1);
18        total += count[i - 1];
19    }
20    return total;
21}

我们还可以从左往右一次遍历来解决。如果从左往右一次遍历判断当前孩子糖果的数量，会有3种情况

1. 当前孩子的评分比左边的高，也就是递增的，那么当前孩子的糖果数量要比左边个多1。

2. 当前孩子的评分等于左边孩子的评分，我们让他降为1,也就是说当前孩子的糖果是1，最终是不是1,后面还需要在判断。

3. 当前孩子的评分低于左边孩子的评分，也就是递减的，这个我们就没法确定当前孩子的糖果了，但我们可以统计递减孩子的数量（我们可以反向思考，这个递减的序列中，最后一个肯定是1，并且从后往前都逐渐增加的）

叙述起来比较拗口，来举个例子，比如数组是[1,3,4,6,8,5,3,1]，8是得分的最高点，8前面的从1开始都是递增的，8后面的从5开始是递减的。也就是说8前面的从1到6，每个孩子的糖果数量分别是[1,2,3,4],那么8后面的从5到1每个孩子的糖果数量分别是[3,2,1]。那么8的糖果数量就是左右两边的最大值加1，也就是4+1=5。

所以8左边糖果的数量是(1+4)*4/2=10，右边的糖果数量是(1+3)*3/2=6，所以总的糖果数量是10+6+5=21。

上面的数组的单调性用图像来表示就是

但实际上数组不一定都是这样的，有可能是这样的，比如[2,5,7,4,3,1,5,7,8,6,4,3]

 1public int candy(int[] ratings) {
 2    int length = ratings.length;
 3    if (length == 1)
 4        return 1;
 5    //记录访问到哪个孩子了
 6    int index = 0;
 7    //记录总共的糖果
 8    int total = 0;
 9    while (index < length - 1) {
10        int left = 0;
11        //统计递增的长度
12        while (index < length - 1 && ratings[index + 1] > ratings[index]) {
13            index++;
14            left++;
15        }
16        int right = 0;
17        //统计递减的长度
18        while (index < length - 1 && ratings[index + 1] < ratings[index]) {
19            index++;
20            right++;
21        }
22        //记录顶点的值，也就是左右两边最大的值加1
23        int peekCount = Math.max(left, right) + 1;
24        //注意这里如果total不等于0要减1，是因为把数组拆分成子数组的时候，低谷的那
25        //个会被拆到两个数组中，如果total不等于0，说明之前已经统计过，而下面会再次
26        //统计，所以要提前减去。
27        if (total != 0)
28            total--;
29        //当前这个子数组的糖果数量就是前面递增的加上后面递减的然后在加上顶点的。
30        total += (1 + left) * left / 2 + (1 + right) * right / 2 + peekCount;
31        //如果当前孩子的得分和前一个一样，我们让他降为1
32        while (index < length - 1 && ratings[index + 1] == ratings[index]) {
33            index++;
34            total++;
35        }
36    }
37    return total;
38}

贪心算法和动态规划不一样，贪心算法只需要在每步做出局部最优解即可。对于这道题来说，如果右边的得分比当前的高，那么右边的糖果只需要比当前的糖果多一个即可，否则就让右边的糖果变为1，这样能满足题目的要求，并且所需要的糖果最少，同理和右边比完之后还要和左边在比较。