- 搜索
日期：2025/04/05 12:38来源：未知 人气：53
有N个孩子排成一列。每个孩子都有一个评分值。您正在为符合以下要求的这些孩子提供糖果：
1.每个孩子必须至少吃一个糖果。
2.评分较高的孩子比邻居得到的糖果更多。
您必须给的最低糖果是多少？
分析
这个问题可以在O（n）时间内解决。
如果邻居的评级值更高，我们总是可以为其分配多一个邻居。但是，要获得最小总数，我们应始终开始按升序加1。我们可以通过从两侧扫描阵列来解决此问题。首先，从左到右扫描阵列，并为所有升序对分配值。然后从右向左扫描并将值分配给降序对。
Java解决方案
publicintcandy(int[] ratings) {
if(ratings == null || ratings.length == 0) {
return0;
}
int[] candies = newint[ratings.length];
candies[0] = 1;
//from let to right
for(int i = 1; i < ratings.length; i++) {
if(ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
} else{
// if not ascending, assign 1
candies[i] = 1;
intresult = candies[ratings.length - 1];
//from right to left
for(int i = ratings.length - 2; i >= 0; i--) {
intcur = 1;
if(ratings[i] > ratings[i + 1]) {
cur = candies[i + 1] + 1;
result += Math.max(cur, candies[i]);
candies[i] = cur;
returnresult;}
最后，开发这么多年我也总结了一套学习Java的资料与面试题，如果你在技术上面想提升自己的话，可以关注我，私信发送领取资料或者在评论区留下自己的联系方式，有时间记得帮我点下转发让跟多的人看到哦。
