1、题目链接
https://leetcode.com/problems/candy/
2、解题思路
这道题的意思是说,有N个小孩子,老师给这N个小孩子的表现打了分,然后需要根据小孩子的得分来给他们分发糖果,当然了,分数高的小孩子得到糖果的数量一般会更多,分发糖果的要求有两个:
- 要求每个小孩子至少都能分到一颗糖果
- 要求在两个相邻的小孩之间,分数高的小孩一定比分数低的小孩分到的糖果要更多
最后问老师最少要准备多少颗糖果;我的第一想法是依次遍历每个小孩的评分,然后根据评分的高低来给至少一个糖果,首先初始第一个小孩得到一颗糖果,那么用他的评分去和他相邻的第二个小孩做比较,如果第二个小孩分数比他高,那么第二个小孩应该得到的糖果数是第一个小孩得到的糖果数+1,否则的话他只能得到1颗糖果,然后依次类推,但是到后面我们会发现,有可能排在前面小孩的分数比排在后面小孩的分数高,但是他们得到的糖都是1,所以我们需要更新一下前面小孩得到的糖果,我们能确定的是排在最后面的小孩最终得到的糖果一定是正确的,所以我们就反向遍历来更新排在前面小孩得到的糖果
3、代码
public int candy(int[] ratings) {
if (null == ratings || ratings.length == 0) {
return 0;
}
int len = ratings.length;
if (len == 1) {
return 1;
}
int[] candy = new int[len];
candy[0] = 1; //初始先给第1个学生一颗糖
// 第一次遍历能保证在最后面的小孩获得的糖果数是正确的
for (int i = 1; i < len; i++) {
candy[i] = ratings[i] <= ratings[i - 1] ? 1 : candy[i - 1] + 1;
}
// 反向遍历更新靠前的小孩子最终能得到的糖果数
for (int i = len - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
candy[i] = candy[i + 1] + 1;
}
}
int sum = 0;
for (int i = 0; i < len; i++) {
sum += candy[i];
}
return sum;
}
网友评论