做介绍英文网站,深圳网站设计与制作公司,广州市建设企业网站报价,wordpress 可视化建站n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求#xff0c;给这些孩子分发糖果#xff1a;
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果#xff0c;计算并返回需要准备的…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循环判断是否为一个递增数列分别从两边不断向另一边求得最大值最后将所有的数总和输出即可解决
总结
本题考察对数组的应用理解题意并想到两边分别向另一边求递增数列即可解决
