题解 | #分糖果问题#

题目：分糖果问题

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

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

示例1**：**输入：[1,1,2]，返回值：4

说明：最优分配方案为1, 1,2

解法一：

思路分析：看似该题目应该属于一个小游戏，感觉可能会很难，下面我们进行分析，因为题目规定，每个人至少需要分一个糖果，所以初始化每个人给一个糖果，接下来我们就从左往右进行遍历，如果右边的孩子得分高，就加一个糖果，这样就保证了从左往右方向得分较多的孩子拿到的糖果多，接下来再从右往左遍历，如果相邻的两个孩子，左边的得分高的话，然而左边的孩子糖果少，就把左边的糖果在右边糖果的基础上加一，最后将所有的糖果数加起来返回即可。

实例分析：[1,1,2,3,1]

首先设定一个结果值res和一个nums(len,1)的容器对象，从左往右进行分析：
图片说明
下面从右往左进行判断糖果的数量是否符合标准，没有发现左边得分高的但是糖果少的，所以直接返回nums容器中值的和。

C++核心代码为：

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int res = 0;
        int len = arr.size();//数组的长度
        vector<int> nums(len,1);//建立一个长度为len的初始化都是1的容器
        for(int i = 0;i < len - 1;i++){//从左往右，找右边的得分高的加糖果
            if(arr[i + 1] > arr[i])
                nums[i + 1] = nums[i] + 1;
        }
        for(int i = len - 1; i > 0;i--){//从右往左，找到左边得分比右边高的，判断是否符合条件
            if(arr[i - 1] > arr[i]){
                nums[i - 1] = max(nums[i - 1],nums[i] + 1);
            }
        }
        for(int num : nums){
            res += num;
        }
        return res;
    }
};

因为在该算法中，一共循环了arr容器两次，循环了nums中的元素一次，所以其时间复杂度为 $O(3N) = O(N)$ ，在该算法中，添加了一个容器对象nums用来存储糖果的数量，所以其空间复杂度为 $O(N)$ 。

解法二：
思路分析：相比于上述方法直接给每个人分发一个糖果再进行判断，我们还可以先给第一个孩子一个糖果，再对接下来的孩子进行判断，判断结果主要分为三种：
1、接下来的孩子的得分等于前一个孩子的得分，那么就给接下来的孩子与之前的那个孩子一样的糖果就行。
2、接下来的孩子的得分大于前一个，那么接下来的孩子要比之前的孩子多一个糖果数。
3、如果接下来的孩子得分小于前一个孩子，那么接下来就无法进行判断，需要依据后面的情况而定。（这种情况不能随便给值，因为随便给值会导致总数出现误差）
C++核心代码：

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int res = 1;//存储最终的结果
        int range = 1;
        int len = arr.size();
        int in = 0,out = 0;//上升和下降的个数
        for (int i = 1; i < len; i++) {
            res++;
            if (arr[i] > arr[i - 1]){
                //当后一个的积分大于前一个的积分
                in++;
                res += in;
                out = 0;
                range = in + 1;
            }
            else if (arr[i] == arr[i - 1]) {
                //当两个值相等的话
                in = 0;
                out = 0;
                range = 1;
            }
            else {
                //其他情况
                in = 0;
                res += out;
                out++;
                if (out >= range) 
                    res++;
            }
        }
        return res;
    }
};

——该算法能够合理的计算出最终的结果值，而且只需要遍历一次全部元素，其时间复杂度为 $O(N)$ ，没有占用存储空间，直接采用res进行记录，所以空间复杂度为 $O(1)$ 。