算法记录
LeetCode 题目:
老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
思路
说明
一、题目
你需要按照以下要求,帮助老师给这些孩子分发糖果:
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?
二、分析
- 需要判断是左右两边的评分大小来进行糖果的分发.
- 可以先朝一个方向上看, 大于前一个则糖果
+1
, 再向另一个方向看. - 需要注意第二次看的时候不能简单的将之前的糖果取出来
+1
, 因为有可能重复发糖果, 只要取其中较大的数量即可.
class Solution {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
candy[0] = 1;
for(int i = 1, j = 1; i < ratings.length; i++) {
if(ratings[i] > ratings[i - 1]) j++;
else j = 1;
candy[i] = j;
}
for(int i = ratings.length - 2, j = 1; i >= 0; i--) {
if(ratings[i] > ratings[i + 1]) j++;
else j = 1;
candy[i] = Math.max(candy[i], j);
}
int num = 0;
for(int i = 0; i < candy.length; i++) num += candy[i];
return num;
}
}
总结
脑筋急转弯。