题解 | #分糖果问题#

一.题目描述
NC130分糖果问题
一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

每个孩子不管得分多少，起码分到一个糖果。
任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组arr代表得分数组，请返回最少需要多少糖果。

二.算法(两次遍历)
图片说明
我们将两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果可以分两种情况：
(1)当arr[i-1]<arr[i]时，i号学生的糖果数量将比i-1号孩子的糖果数量多。
(2)当arr[i]>arr[i+1]时，i号学生的糖果数量将比i+1号孩子的糖果数量多。
具体地，我们举例从左到右遍历该数组，假设当前遍历到位置i，如果有arr[i-1]<arr[i]，那么i号学生的糖果数量将比i-1号孩子的糖果数量多，我们令cnt[i]=cnt[i-1]+1即可，否则我们令cnt[i]=1。
下面给出完整代码：

class Solution {
public:
    int candy(vector<int>& arr) {
        int len=arr.size();
        int cnt[len+5];
        for(int i=0;i<len+5;i++) cnt[i]=1;
        int sum=0;
        //从左往右遍历
        for(int i=1;i<len;i++){
            if(arr[i]>arr[i-1]){
                cnt[i]=cnt[i-1]+1;
            }
        }
        //从右往左遍历
        for(int i=len-1;i>0;i--){
            if(arr[i-1]>arr[i]){
                cnt[i-1]=max(cnt[i-1], cnt[i]+1);
            }
        }
        for(int i=0;i<len;i++){
            sum+=cnt[i];
        }
        return sum;
    }
};

时间复杂度： $O(n)$ ，其中n是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度： $O(n)$ ，其中n是孩子的数量。我们需要保存所有的左规则对应的糖果数量。
优缺点：在时间上需要做两次遍历，而且空间复杂度高，但是实现起来简单，便于实现
三.算法
我们从左到右枚举每一个同学，记前一个同学分得的糖果数量为pre：
如果当前同学比上一个小孩评分高，说明我们就在最近的递增序列中，直接分配给该小孩pre+1个糖果即可。
否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。这样，我们只要记录当前递减序列的长度a，最近的递增序列的长度b和前一个同学分得的糖果数量pre即可。下面是完整代码:

class Solution {
public:
    int candy(vector<int>& arr) {
        int n =arr.size();
        int ans=1,a=1,b=0,pre=1;
        //ans返回最少需要的糖果数
        //pre表示初始需要增加的糖果量
        //a,b表示连续上升和下降的个数
        for (int i=1;i<n;i++) {
            //对于非上升序列
            if (arr[i]>=arr[i-1]) {
                b=0;
                //如果是当前和上一位相对 那么初始的pre可以为1
                if(arr[i]==arr[i-1]){
                    pre=1;
                } else {
                    //不是那么pre就要递增
                    pre+=1;
                }
                ans+= pre;
                a=pre;
            } else {
                b++;//上升的个数递增
                if (a==b) b++;
                ans+=b;
                pre=1;
            }
        }
        return ans;
    }
};

时间复杂度： $O(n)$ ，其中n是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度： $O(1)$ ，我们只需要常数的空间保存若干变量。
优缺点：在时间上需要做两次遍历，但是空间复杂度低。