分发糖果

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

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

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

示例 1:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/candy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution{
    public static int candy(int[] ratings) {
        if (ratings.length == 0) return 0;
        if (ratings.length < 2) return 1;

        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);                                  //每个孩子必须有一颗糖

        if (ratings[0] > ratings[1]) {                               //第0个孩子，边界条件
            candy[0]++;
        }

        for (int i = 1; i < ratings.length; i++) {                   //从前往后，如果后面的孩子的得分大于当前的孩子的得分，后面的孩子的糖比当前孩子多一个
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 1; i > 0; i--) {               //从后往前，如果前面的孩子的得分大于后面的孩子，
                                                                     //那么要看前面孩子的糖的数量是否已经大于后面的孩子，
                                                                     //如果已经大于了，那么只需要再分给他一块，
                                                                     //如果没有大于，直接把后面孩子糖的数量加1给前面的孩子（原来的糖收回）
            if (ratings[i - 1] > ratings[i]) {
                if (candy[i - 1] <= candy[i]) {
                    candy[i - 1] = Math.max(candy[i - 1] + 1, candy[i] + 1);
                }
            }
        }

        int sum = 0;
        for (int i = 0; i < candy.length; i++) {                    //统计分发的糖的数量
            sum += candy[i];
        }
        return sum;
    }
}

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

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

• 我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。

• 同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。

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

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;                                            //递减序列的长度
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;   //前一个同学得分的糖果数量
                ret += pre;
                inc = pre;                                          //递增序列的长度
            } else {
                dec++;
                if (dec == inc) {
                    dec++;
                }
                ret += dec;
                pre = 1;
            }
        }
        return ret;
    }
}

参考文献

作者：LeetCode-Solution 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信