题意概述

• 给定一个得分数组，按照该数组给孩子分糖果
• 满足下列两个要求
• 每个孩子不管得分多少，起码分到一个糖果。
• 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
• 问最少需要多少糖果。

方法一：两次遍历

思路与具体做法

因为相邻的得分高的孩子要多拿一些糖果，所以对于每个孩子，依次和左右孩子比较

• 第一次从左到右循环孩子，如果当前孩子分数比前一个孩子分数高，则当前孩子的糖果数应是前一个孩子糖果数+1，否则当前孩子的糖果数就是1
• 第二次从右向左循环孩子，如果当前孩子分数比前一个孩子分数高，则当前孩子的糖果数应是前一个孩子糖果数+1，否则当前孩子的糖果数就是1
• 两次循环中当前孩子糖果数的最大值就是满足题设条件下该孩子分得糖果的最小值，累加这个值即得到最终答案

class Solution {
public:
    int candy(vector<int>& arr) {
    	int size=arr.size();
    	vector<int>left(size,0);
		for(int i=0;i<size;i++){
			if(i>0&&arr[i-1]<arr[i])left[i]=left[i-1]+1;
			else left[i]=1;
		} 
		int right=1,ans=0;
		for(int i=size-1;i>=0;i--){
			if(i<size-1&&arr[i]>arr[i+1])right++;
			else right=1;
			ans+=max(left[i],right);
		}
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历了两次长度为n的数组
• 空间复杂度：$O(n)O(n)$，用到了一个长度为n的辅助数组来保存从左到右遍历下的当前孩子分得糖果数

方法二：一次遍历

思路与具体做法

• ans为总共需要糖果数，pre为前一人分得糖果数，len_a为连续上升序列长度，len_b为连续下降序列长度
• 从位序为1的位置开始遍历，和前一个元素作比较。
• 如果当前元素比前一元素大，说明在最近的递增序列中，分配给该孩子pre+1个糖果；
• 否则就在一个递减序列中，直接分配给当前孩子一个糖果，并将该孩子所处递减序列中所有孩子都再分配一个糖果。
  • 额外分配的糖果数量可由当前的递减序列长度计算得到
  • 当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个孩子也并进递减序列中。

class Solution {
public:
    int candy(vector<int>& arr) {
		int size=arr.size(),ans=1,pre=1,len_a=1,len_b=0;//ans为总共需要糖果数，pre为前一人分得糖果数，len_a为连续上升序列长度，len_b为连续下降序列长度 
		for(int i=1;i<size;i++){
			if(arr[i]>=arr[i-1]){//非下降序列 
				len_b=0;//递减序列长度置0
				if(arr[i]>arr[i-1])pre+=1;//决定当前孩子的糖果数 
				else pre=1; 
				ans+=pre;//当前孩子的糖果数计入总数 
				len_a=pre;//当前孩子的糖果数也即前面紧邻连续上升序列长度 
			}else{//下降序列 
				len_b++;//递减序列长度加一， 
				if(len_b==len_a)len_b++;//当前递减序列长度等于前面紧邻递增序列长度时
				ans+=len_b;//递减序列中的每一个元素均加一，共加序列长度 
				pre=1;//递减序列中末尾孩子的糖果数为一 
			}
		} 
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历了一次长度为n的数组
• 空间复杂度：$O(1)O(1)$，未用到额外空间。