分发糖果
问题描述
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
解题思路
此问题解法为：贪心算法
只要比相邻位置的孩子评分高那就比相邻位置的糖果数加一
那么：
第一次循环从左到右，右边比左边大时，candy[i+1] = candy[i] +1;
第二次循环从右到左，左边比右边大时，candy[i-1] = candy[i] +1;
注意：第二次循环时不是只要大就加1，而是为了不与第一循环冲突，加了之后会变大时才加一
算法提升
为了优化算法的运行时间，最好代码里只有两次最主要的循环，那么就要把糖果数组的初始化与第一次循环结合起来，来减少for循环。
对于内存占用的优化，就是不必要的变量就不要申请，所以此题中应尽量只申请一个数组canduNum，对于for循环中的：i，函数内申请i会一直伴随着函数的运行，知道函数结束时释放。for循环内申请，循环结束时就会被释放。一般采用for循环内申请，因为当程序较大时，函数内申请会占用内存时间较长，cpu负担增大，溢出风险增加（只能说是震惊）。
解题代码
int candy(int* ratings, int ratingsSize){int candyNum[ratingsSize];candyNum[0] = 1; for (int i = 0; i < ratingsSize-1; i++){if(ratings[i+1] > ratings[i]) candyNum[i+1] = candyNum[i] + 1;else candyNum[i+1] = 1;}for (int i = ratingsSize-1; i > 0; i--){if(ratings[i-1] > ratings[i]) {if (candyNum[i] + 1 > candyNum[i-1]){candyNum[i-1] = candyNum[i] + 1;}} }for(int i = 1; i< ratingsSize; i++) {candyNum[0] += candyNum[i];}return candyNum[0];
}
有错误和更好的方法欢迎指正