[数据结构与算法]LeeCode 135 分发糖果

分发糖果

问题描述

老师想给孩子们分发糖果，有 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];
}

有错误和更好的方法欢迎指正