题解 | #分糖果问题#

题意：

给定一个数组，每一个数组元素对应另外一个数组值，求另外一个数组值的总和。
要求：每一个数组对应的值不小于1；任意两个相邻的数组元素，大的数组元素对应的值更大，相同无限制。

方法一：贪心

题目主要的难点是在于实现“任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果”，因此我们利用贪心的思路：从左往右遍历一遍，如果右边评分比左边评分高，右边糖果数就更新为左边糖果数+1；再从右向左遍历一边，如果左边评分比右边评分高，此时更新为max(左边糖果数,右边糖果数+1)。

代码如下：

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int n=arr.size();
        if(n<=1)
            return n;
        //额外数组存储每个人分配的糖果数
        vector<int> candyNum(n,1);
        //从左向右遍历，右边分数大于左边的糖果数加1
        for(int i=0;i<n-1;i++){
            if(arr[i]<arr[i+1])
               candyNum[i+1]=candyNum[i]+1;
        }
        //从右往左遍历，左边分数大于右边的更新糖果数
        for(int i=n-1;i>0;i--){
            if(arr[i]<arr[i-1])
                candyNum[i-1]=max(candyNum[i]+1,candyNum[i-1]);
        }
        //返回最少需要的总糖果数
        int ans=0;
        for(int x:candyNum)
            ans+=x;
        return ans;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历数组两次。
空间复杂度： $O(n)$ ，存储每个人分配糖果的数组candyNum， $O(n)$ 。

但是本方法不完全满足题目时间复杂度 $O(n)$ ,空间复杂度 $O(1)$ 的要求。

方法二：

解题思路：

想要用空间复杂度O(1)的解法，就需要不记录每个人分糖果的数量，而是在从左向右遍历的过程中寻找分配糖果的规律：根据孩子的得分来看，整个糖果分配的情况是一个折线图，且满足以下规律:

1.递增序列每次比前次加一。
2.递减序列的糖果数取决于递减序列长度与递增序列长度之间的大小关系：（1）若递减序列长度decLen小于递增序列长度incLen，则糖果数为1,2,3,……,decLen；（2）否则在此基础上还需要更新递增序列最后一个元素的值，从incLen更新为decLen。
3.每次遇到相同的得分，可视为清零重新开始。

以得分情况[1,2,3,4,3,2,2,1,4]为例，其糖果分配情况如下:

代码说明：

用一个变量ans作为返回结果，表示最少需要分配的糖果总数；pre表示上一个人的糖果数，incLen表示递增序列长度，decLen表示递减序列长度。对于递增序列，只需要每次更新为pre+1，并将其加入ans中即可；对于递减序列，我们需要确定递减序列与递增序列之前的长度关系。
decLen++; ans+=decLen是对递减序列1,2,3,……的累加，实际上的序列是……,3,2,1的累加，最终结果ans不变。
if(decLen==incLen) decLen++;是对递减序列和递增序列之间的长度判断，在decLen<incLen的情况下，不需要考虑递增序列最后一位，因为右边的是小于它的，但是当decLen==incLen时，需要加该一位加入到递减序列中，因此decLen++。

代码如下：

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int n=arr.size(),ans=1;
        //分别代表前一个孩子的糖果数，递增序列长度，递减序列长度。
        int pre=1,incLen=1,decLen=0;
        for(int i=1;i<n;i++){
            if(arr[i]>=arr[i-1]){
                //更新pre值，总糖果数ans，以及incLen和decLen
                if(arr[i]==arr[i-1])
                    pre=1;
                else
                    pre=pre+1;
                ans+=pre;
                incLen=pre;
                decLen=0;
            }
            else{
                //更新decLen,ans和pre
                decLen++;
                if(decLen==incLen)
                    decLen++;
                ans+=decLen;
                pre=1;
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历数组。
空间复杂度： $O(1)$ ，常数个临时变量。