一. 简介

本文记录力扣网上涉及数组方面的编程题：分发糖果。

这里使用贪心算法的思路来解决（求局部最优，最终求全局最优解）：每个孩子只需要考虑与相邻孩子的相对关系。

二. 力扣网编程135题：分发糖果（遍历两遍数组）

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

解题思路一：（遍历两遍数组）

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理：

左规则：ratings[i-1] < ratings[i]，i号孩子的糖果比 i-1号孩子的糖果数量多；

右规则：ratings[i] > ratings[i+1]，i号孩子比 i+1号孩子的糖果数量少；

遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

具体方法如下：

1. 定义一个数组left[ratingsSize]，用于存放满足左规则的糖果数目；变量 right 存放满足右规则的糖果数目；

1. 满足左规则：从前往后遍历数组，若 ratings[i-1] < ratings[i]，则 left[i] = left[i-1] +1，否则，left[i] = 1；

2. 满足右规则：类似处理，不过是从后往前进行遍历。

若 ratings[i] > ratings[i+1]，则 right += 1，否则，right =1。在遍历过程中，求 满足左规则和右规则的糖果数目进行比较，求最大值，同时进行累计。

C语言实现如下：

//遍历两次数组，满足条件
//1.左规则：ratings[i-1] < ratings[i], 则ratings[i]=ratings[i-1]+1
//2.右规则：ratings[i] > ratings[i+1],则ratings[i]= ratings[i+1]+1
int candy(int* ratings, int ratingsSize) {int i;int count = 0;int left[ratingsSize];//从前往后遍历//左规则：ratings[i-1] < ratings[i], 则ratings[i]=ratings[i-1]+1for(i = 0; i < ratingsSize; i++) {if((i>0) && (ratings[i-1] < ratings[i])) {left[i] = left[i-1]+1;}else {left[i] = 1;}}int right = 0;//从后往前遍历//右规则：ratings[i] > ratings[i+1],则ratings[i]= ratings[i+1]+1for(i = ratingsSize-1; i >= 0; i--) {if((i < ratingsSize-1) && (ratings[i] > ratings[i+1])) {right += 1;} else {right = 1;}count += fmax(left[i], right);} return count;
}

可以看出，贪心算法的解法的时间复杂度为 O(n)，空间负责度为O(n)。

第二种实现如下，也是同样的思路（贪心算法）：

//贪心算法：
//局部最优：每个孩子只需要关心和她相邻的关系
int candy(int* ratings, int ratingsSize) {int i;int candies[ratingsSize];int right = 0;int count = 0;memset(candies, 0, ratingsSize*sizeof(int));for(i = 0; i < ratingsSize; i++) {candies[i] = 1;}//遵循左规则：从左到右遍历//如果 ratings[i-1] < ratings[i]for(i = 0; i < ratingsSize; i++) {if((i>0) && (ratings[i-1] < ratings[i])) {candies[i] = candies[i-1] + 1;}}//遵循右规则：从右向左遍历//如果 ratings[i] > ratings[i+1]for(i = ratingsSize-1; i>=0; i--) {if((i<ratingsSize-1) && (ratings[i] > ratings[i+1])) {right += 1;}else {right = 1;}count += fmax(candies[i], right);}return count;
}