题目描述
n
个孩子站成一排。给你一个整数数组 ratings
表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
示例 1:
输入:ratings = [1,0,2] 输出:5 解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2:
输入:ratings = [1,2,2] 输出:4 解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。
提示:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
解题思路:
1.分别从左向右和从右向左遍历两次数据,分别求出最小被分得的糖果数量,每个人最终分得的糖果数量即为这两个数量的最大值。
2.将数组中数字分为上升和下降两个序列,如果是上升序列,糖果数+1,如果是下降序列,给当前元素分一颗糖,然后下降序列元素的糖果数同时+1,如果两个元素相同,则将后面的元素的糖果数设为1,最后计算总的糖果数。
题解:
思路一:
class Solution {
public int candy(int[] ratings) {
int n=ratings.length;
int[] left=new int[n];
for(int i=0;i<n;i++)
{
if(i>0&&ratings[i]>ratings[i-1])
{
left[i]=left[i-1]+1;
}else
{
left[i]=1;
}
}
int right=0,ret=0;
for(int i=n-1;i>=0;i--)
{
if(i<n-1&&ratings[i]>ratings[i+1])
{
right++;
}else
{
right=1;
}
ret +=Math.max(left[i],right);
}
return ret;
}
}
思路二:
class Solution {
public int candy(int[] ratings) {
//获取评分数组的长度
int n=ratings.length;
//初始化返回的糖果数为1
int ret=1;
//初始化递增,递减序列的长度和前一个孩子的糖果数
int inc=1,dec=0,pre=1;
for(int i=1;i<n;i++)//从第二个孩子开始遍历
{
if(ratings[i]>=ratings[i-1]){//当前孩子的评分不小于前一个孩子
//递增序列
dec=0;//重置递减序列长度
pre=ratings[i]==ratings[i-1]?1:pre+1;//如果评分相同,重置pre为1,否则pre递增
ret+=pre;//将当前孩子的糖果数加在总糖果数上
inc=pre;//更新递增序列的长度
}else{
//递减序列
dec++;
if(dec==inc){// 当递减序列长度和递增序列长度相等时,把最近的递增序列的最后一个同学也并进递减序列中
dec++;
}
ret+=dec;// 将当前孩子的糖果数加到总糖果数上
pre=1;// 重置前一个孩子的糖果数,因为下一个孩子可能开始一个新的序列
}
}
return ret;// 返回最小糖果数
}
}