分糖果问题

问题描述：一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下： 
1. 每个孩子不管得分多少，起码分到一个糖果。 
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制) 
给定一个数组arr代表得分数组，请返回最少需要多少糖果。 
[要求] 时间复杂度为$O(N)$, 空间复杂度为$O(1)$
示例
输入：[1,1,2]
返回值：4
说明：最优分配方案为1,  1，2

方法一

思路分析

     为使每个孩子都能得到一个糖因此，首先先给每个孩子一个糖果，接着直接使用循环遍历的办法，从左往右遍历，右边得分高的糖果数比左边孩子多一个。从右往左遍历，如果左边孩子分数高，并且左边孩子糖果数较小，则糖果数为右边孩子的加1。最后统计所有的糖果数量。

C++核心代码 

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();
        vector<int> temp(n,1);
        for(int i=1;i<n;i++)
        {
            if(arr[i-1]<arr[i])
            {
                temp[i]=temp[i-1]+1;//从左往右遍历，右边得分高的糖果数比左边孩子多一个
            }
        }
        for(int i=n-1;i>0;i--)
        {
            if(arr[i]<arr[i-1])
            {
                temp[i-1]=max(temp[i-1],temp[i]+1);//从右往左遍历，如果左边孩子分数高，并且左边孩子糖果数较小，则糖果数为右边孩子的加1
            }
        }
        int sum=0;
        for(int i=0;i<n;i++)
            sum+=temp[i];//统计所有的糖果数
        return sum;
    }
};

复杂度分析

  • 时间复杂度：需要两次非嵌套循环遍历，因此时间复杂度为$O(N)$
  • 空间复杂度：需要借助于一个数组，空间复杂度为$O(N)$
   

方法二

思路分析

     上面的办法空间复杂度不符合题目要求，因此为了降低空间复杂度，只需要设置一个变量用于存储糖果数，那么需要从左开始遍历，为了使相邻两个孩子中得分高的,需要找到数组中分数连续下降的几个元素以及连续上升的元素，如果统计到连续下降的则将得分最低的糖果数置为1，其余连续增加1，如果统计到连续上升的则将得分最低的糖果数置为1，其余连续加1。
具体实现过程如下：
  • 数组从左到右遍历，如果下一个同学的得分较高，则当前处于一个递增序列，计算递增序列的长度rise，递增序列分配的糖果数1+2+3+...+n
  • 如果下一个同学的得分较低，则当前处于递减序列，计算递减序列的长度decline，那么从递减序列中最后一个元素开始往前推每往前一个加一个糖果，增加的糖果数为1+2+3+...+n
  • 然后我们还要看第一个开始减小的同学的前一个同学需不需要追加糖果，只要比较rise和decline的大小，加到结果res中即可

图解示例

得分数组：[5,4,3,6,7,4,3,2]使用横坐标表示

如图所示，对于一个[5,4,3,6,7,4,3,2]，一定会寻找到连续的升序序列和连续的降序序列，设置rise表示升序序列的长度，decline表示降序系列的长度。例如[5,4,3]表示降序序列，为使糖果数最少，分配糖果数为[3,2,1]，[3,6,7]升序序列分配的糖果数为[1,2,3]，[7,4,3,2]降序序列分配的糖果数为[4,3,2,1]，可以通过序列长度求得糖果总数；但是注意到有些元素在不同的序列中都存在，因此对于这些元素的处理则根据升序序列与降序序列的长度进行确定,例如对于元素7,升序序列中分配糖果数为3，但在降序序列中分配糖果数为4，那么根据序列长度大的确定，因此总的糖果分配为[3,2,1,2,4,3,2,1]。

python核心代码 

#
# pick candy
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def candy(self , arr ):
        # write code here
        def nextMinIndex(arr, start):
            for i in range(start, len(arr)-1):
                if arr[i+1] >= arr[i]:#寻找升序序列
                    return i
            return len(arr) - 1 

        def rightCands(left, right):
            n = right - left + 1
            return n * (n+1) // 2  #求解升序序列或者降序序列的增值=1+2+3+...+n


        if arr == None&nbs***bsp;len(arr) == 0:
            return 0
        index = nextMinIndex(arr, 0)
        res = rightCands(0, index)
        index += 1
        rise = 1
        while index != len(arr):#从左到右遍历数组
            if arr[index] > arr[index-1]:#升序序列
                rise += 1#升序序列的长度
                res += rise
                index += 1
            elif arr[index] < arr[index-1]:#开始处于降序序列，计算降序序列的长度与增值
                next = nextMinIndex(arr, index-1)
                res += rightCands(index-1, next)
                decline = next - index + 2#降序序列的长度
                res -= decline if decline < rise else rise
                rise = 1
                index = next + 1
            else:
                res += 1#如果两个相邻分值相同，则归为升序序列
                rise = 1
                index += 1
        return res

复杂度分析

  • 时间复杂度：从左到右循环遍历以此数组，时间复杂度为$O(N)$
  • 空间复杂度：借助于几个变量，因此空间复杂度为$O(1)$