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;                                            // 前方递减序列长度为0pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1; // 若相邻两孩子评分相同，则只给当前孩子1个糖果，否则比前一个多1ret += pre;                                         // 累加当前糖果数inc = pre;                                          // 递增数列恰好从1开始递增，故inc = pre}else{dec++;          // 递减数列长度+1：由于初始dec = 0，故此时dec恰好为当前递减数列长度if (dec == inc) // 递增数列长度 = 递减数列长度dec++;      // 递减数列长度+1，将前方最近递增序列末尾元素归并入递减序列ret += dec;     // 递减序列中的每一个元素均+1，共+decpre = 1;        // 递减数列当前（末尾）元素糖果数为1}return ret;
}

分析：

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

总结：

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