力扣例题：分发糖果

n?个孩子站成一排。给你一个整数数组?ratings?表示每个孩子的评分。

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

• 每个孩子至少分配到?1?个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的?最少糖果数目?。

案例：

输入：ratings = [1,3,5,3,2,1]
输出：13

?题目思路：

每个孩子至少得到一个糖果，对于任意两个孩子，评分最高的孩子会获得更多的糖果，要求计算需要准备的最少的糖果数。那我们就可以利用贪心算法。用p[]数组来表示每一个孩子得到的糖果数依次遍历每个孩子。假设遍历到第i个孩子。如果第i-1个孩子的评分比较X小，ratings[i-1]<ratings[i]，那么我们就给第i-1个孩子比i多一颗糖果。也就是p[i]=p[i-1]+1。但是如果第i-1个孩子和第i个孩子的评分一样大，ratings[i]==ratings[i-1]，由于评分相等的没有做要求，所以我们就把它设为最小的数1，也就是p[i]=1。但是如果第i-1个孩子比第i个孩子的评分大的话，那么这时候p[i]<p[i-1]的，但是这时候我们要给p[i]赋值为什么呢，如果总结赋值为1，那么如果第i+1个孩子比第i给孩子小，p[i]>p[i+1]，那么这时候只能给p[i+1]赋值为0，又不符合题意。所以我们就需要另加讨论。

我们可以想到，这种情况是一种递减的情况，我们可以用dec标记一下递减结束的区间，假设递减开始的是3，递减结束的时候是-2.那么也就是说我们需要把这个递减区间内的每个小孩的糖果都假设3，才能保证每个小孩至少有一个糖果。我们也可以换一个思路，递减结束的时候小孩的糖果数就是为1，那么倒数第二个就是2，一直到递减开始。我们就可以反向加，设一个dec来表示递减的个数。我们用ans来表示最后输出的最少糖果数目。dec，ans初始值设置为0。每次递减dec++，ans+=dec。特别注意的是，当碰到递增数列的最大值的时候，也就是我们刚开始递减的时候的那个数，我们的递减数列中肯定有这个数，我们就把dec++，直接跳转取它的后一个数再次dec++。我们另设一个inc代表递增数列的长度最后递减结束后就该是递增区间，按照之前的想法，用pre记录前面一个的糖果值，每次如果相等pre=1，否则pre+=1；最后ans+=pre。

案例分析：

我们可以看到，在递增区间的时候第三个应该是被赋值为3的，但是由于右边递减区间比左边递增区间大一，当遍历到第五个的时候，dec就加到3了，所以如果还存在下一个第六个就应该dec++，使得原本第三个的3加到4。以此得到正确答案。

总结：

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

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

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

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

代码展现：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        int ans=1;
        int inc=1,dec=0,pre=1;
        for(int i=1;i<n;i++){
            if(ratings[i]>=ratings[i-1]){
                dec=0;
                if(ratings[i]==ratings[i-1])pre=1;
                else pre+=1;
                ans+=pre;
                inc=pre;
            }
            else {
                dec++;
                if(dec==inc)dec++;
                ans+=dec;
                pre=1;
            }
        }
        return ans;
    }
};

代码解释：

ans表示为最后需要返回的最小糖果数，inc为递增区间长度，pre为递增区间的上一个小孩的糖果数，dec为递减区间长度。

复杂度：

时间复杂度：O(n)

空间复杂度：O(1)