首页 > 代码库 > LeetCode Candy
LeetCode Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
解法：从左到右比较，第一个发1个，下一个比前一个rating高就+1，否则发1个。
然后从右到左，最后一个发1个，前一个比后一个rating高就+1,否则发1个。
取两次得到的值的最大值，然后累加。
1 public class Solution { 2 public int candy(int[] ratings) { 3 int[] leftCandys = new int[ratings.length]; 4 int[] rightCandys = new int[ratings.length]; 5 int[] candys = new int[ratings.length]; 6 int sum=0; 7 leftCandys[0]=1; 8 for (int i = 0; i < ratings.length-1; i++) { 9 if (ratings[i]<ratings[i+1]) {10 leftCandys[i+1]=leftCandys[i]+1;11 }else {12 leftCandys[i+1]=1;13 }14 }15 16 rightCandys[ratings.length-1]=1;17 for (int i = ratings.length-1; i >0; i--) {18 if (ratings[i]<ratings[i-1]) {19 rightCandys[i-1]=rightCandys[i]+1;20 }else {21 rightCandys[i-1]=1;22 }23 }24 25 for (int i = 0; i < candys.length; i++) {26 candys[i]=Math.max(leftCandys[i], rightCandys[i]);27 sum=sum+candys[i];28 }29 return sum;30 }31 }
LeetCode Candy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。