题解 | #分糖果问题#

分糖果问题

1、题意重述

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

1. 每个孩子不管得分多少，起码分到一个糖果。
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。

换句话说，就是每个孩子必须拿到一个糖果，并且得分高的孩子拿到的糖果也要相应得多。

2、思路整理

使用贪心的思想：

Step1:首先从左到右遍历，利用贪心的思想，如果右边的孩子比左边孩子的分数高，那么就多的一颗糖。

Step2：再从右向左遍历，如果左边的孩子比右边孩子的得分高，则孩子的糖数更新为max(左边孩子的糖果数，右边孩子的糖果数+1)，最终得到答案。

3、代码实现

class Solution {
public:
    int candy(vector<int>& arr) {
        // write code here
        int n=arr.size();
        if(n<=1)
            return n;
        vector<int> candy(n,1);
        //从左向右遍历，右边分数大于左边，则右边的糖果数加1
        for(int i=0;i<n-1;i++){
            if(arr[i]<arr[i+1])
               candy[i+1]=candy[i]+1;
        }
        //从右往左遍历
        for(int i=n-1;i>0;i--){
            if(arr[i]<arr[i-1])
                candy[i-1]=max(candy[i]+1,candy[i-1]);
        }
        int ans=0;
        for(int x:candy)
            ans+=x;
        return ans;  //返回结果
    }
};

4、复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(N)O(N)$。

空间复杂度：使用了vector candy，因此空间复杂度为$O(N)O(N)$，N为candy的大小。