糖果分配java

糖果分配java"/>

糖果分配java

有N个孩子排成一列。每个孩子都有一个评分值。您正在为符合以下要求的这些孩子提供糖果：

1.每个孩子必须至少吃一个糖果。

2.评分较高的孩子比邻居得到的糖果更多。

您必须给的最低糖果是多少？

分析

这个问题可以在O(n)时间内解决。

如果邻居的评级值更高，我们总是可以为其分配多一个邻居。但是，要获得最小总数，我们应始终开始按升序加1。我们可以通过从两侧扫描阵列来解决此问题。首先，从左到右扫描阵列，并为所有升序对分配值。然后从右向左扫描并将值分配给降序对。

Java解决方案

public int candy(int[] ratings) {

if (ratings == null || ratings.length == 0) {

return 0;

}

int[] candies = new int[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;

}

}

int result = candies[ratings.length - 1];

//from right to left

for (int i = ratings.length - 2; i >= 0; i--) {

int cur = 1;

if (ratings[i] > ratings[i + 1]) {

cur = candies[i + 1] + 1;

}

result += Math.max(cur, candies[i]);

candies[i] = cur;

}

return result;}

最后，开发这么多年我也总结了一套学习Java的资料与面试题，如果你在技术上面想提升自己的话，可以关注我，私信发送领取资料或者在评论区留下自己的联系方式，有时间记得帮我点下转发让跟多的人看到哦。