leetcode做题笔记135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

思路一：模拟题意

int candy(int *ratings, int ratingsSize)
{
    int ret = 1, inc = 1, dec = 0, pre = 1;
    for (int i = 1; i < ratingsSize; i++)                       // 由于第0个孩子已赋初值，故从第1个孩子开始遍历
        if (ratings[i] >= ratings[i - 1])                       // 递增数列和两元素相等可同时处理，只需在下面加一个判断即可
        {
            dec = 0;                                            // 前方递减序列长度为0
            pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1; // 若相邻两孩子评分相同，则只给当前孩子1个糖果，否则比前一个多1
            ret += pre;                                         // 累加当前糖果数
            inc = pre;                                          // 递增数列恰好从1开始递增，故inc = pre
        }
        else
        {
            dec++;          // 递减数列长度+1：由于初始dec = 0，故此时dec恰好为当前递减数列长度
            if (dec == inc) // 递增数列长度 = 递减数列长度
                dec++;      // 递减数列长度+1，将前方最近递增序列末尾元素归并入递减序列
            ret += dec;     // 递减序列中的每一个元素均+1，共+dec
            pre = 1;        // 递减数列当前（末尾）元素糖果数为1
        }
    return ret;
}

分析：

本题要求需要准备的最少糖果数目，理解题意可以知道每个孩子向左右两边满足递减的要求，可以编写一个for循环，判断是否为一个递增数列，分别从两边不断向另一边求得最大值，最后将所有的数总和输出即可解决

总结：

本题考察对数组的应用，理解题意并想到两边分别向另一边求递增数列即可解决