135.分发糖果

发表于： 分类于：
字数： 1429 阅读：≈ 3分钟

🍬135.分发糖果

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

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

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中，评分高的孩子必须获得更多的糖果。
  • 相邻孩子评分相同是可以分配相同的糖果

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

示例

示例 1:

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

示例 2:

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

思路

基本思想

容器不能排序，否则最开始相邻的孩子可能不相邻，拆解规则二，相邻的孩子中分数高的糖果多

这个规则可以拆分成两个规则，分数比左边高，糖果比左边多，分数比右边高，糖果比右边多

初始状态下每个小孩都有一个糖果

  1. 右大于左，右边小孩糖果数=左边小孩糖果数+1
  2. 左大于右，左边小孩糖果数=右边小孩糖果数+1

所以需要经过两次统计，两次统计的结果综合起来才是最终的结果

执行流程

  1. 从前向后遍历，如果右边小孩的分数大于左边小孩，糖果数就比左边小孩多1，完成第一阶段的统计

  2. 接下来判断左边小孩是不是比右边小孩分数高，是的话糖果数也要变化，这里必须从后向前变化

    并且统计左大于右的情况时，如果出现右边小孩的糖果+1还是小于当前左边小孩的糖果数，说明左边的左边限制了这个数目，直接选取大的即可，这个不好理解的话可以想象，当前这个左边小孩的糖果数已经被左边限制住了，右边的小孩也限制住了当前的糖果数，相当于两边都有限制，为了两边都满足条件，就取最大的结果

    相当于宁可多发，也不能少发

因为统计的是左>右的情况，右边的结果直接影响到左边的结果，所以右边的要先统计

想不明白可以拿[1,2,87,87,87,2,1]举例，如果从前向后统计左>右的情况得到的糖果数组为

[1,2,3,1,2,2,1],而从后向前统计得到的糖果数组为[1,2,3,1,3,2,1]，原因就是从前向后统计最右边的2的影响无法传递给最右边的87，因为我们此时是统计左>右，而最右边的87的糖果数需要依赖于最右边的2，所以需要从后往前统计

可以将统计和合并的工作放在一起，不用统计完成之后再合并

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    //统计完成之后再合并
    int candy(vector<int>& ratings) {
        //初始状态下每个人一个糖果
        vector<int> candy(ratings.size(),1);
        int res=0;
        //统计右>左的情况
        for(int i=1;i<ratings.size();++i){
            if(ratings[i]>ratings[i-1]){
                candy[i]=candy[i-1]+1;
            }
        }
        //统计左>右的情况
        for(int i=ratings.size()-2;i>=0;--i){
            if(ratings[i]>ratings[i+1]){
                //取大的情况
                candy[i]=max(candy[i+1]+1,candy[i]);
            }
        }
        //将两种情况合并，宁可多发也不能少发
        //统计结果
        for(int i=0;i<candy.size();++i){
            res+=candy[i];
        }
        return res;
    }
};

如果理解不了上面的代码，可以看下面的代码，将两种情况分开统计，最后合并

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    //统计完成之后再合并
    int candy(vector<int>& ratings) {
        //初始状态下每个人一个糖果
        vector<int> candy1(ratings.size(),1);
        vector<int> candy2(ratings.size(),1);
        int res=0;
        //统计右>左的情况
        for(int i=1;i<ratings.size();++i){
            if(ratings[i]>ratings[i-1]){
                candy1[i]=candy1[i-1]+1;
            }
        }
        //统计左>右的情况
        for(int i=ratings.size()-2;i>=0;--i){
            if(ratings[i]>ratings[i+1]){
                candy2[i]=candy2[i+1]+1;
            }
        }
        //将两种情况合并，宁可多发也不能少发
        //统计结果
        for(int i=0;i<candy1.size();++i){
            candy1[i]=max(candy1[i],candy2[i]);
            res+=candy1[i];
        }
        return res;
    }
};

总结

将规则2进行拆分，分为左>右和右>左，在统计每一种情况时统计的方向不一样

左>右时需要从后向前统计，这样先统计右边，右边的影响才能传递到左边

右>左时需要从前向后统计，这样先统计左边，左边的影响才能传递到右边

因为将规则2进行拆分，所以统计完成之后还需要进行合并，从两次统计的结果中取一个大的，理解为宁可多分，也不要少分