一. 简介
本文记录力扣网上涉及数组方面的编程题：分发糖果。
这里使用贪心算法的思路来解决（求局部最优，最终求全局最优解）：每个孩子只需要考虑与相邻孩子的相对关系。
二. 力扣网编程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]+1
for(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]+1
for(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;
}