首页 > 代码库 > [leetcode]Candy
[leetcode]Candy
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?
算法思路：
双向各扫描一次，第一次正向扫描，寻找递增序列，遇到ratings[i] > ratings[i - 1]，则将candy[i] = candy[i - 1]；
第二次寻找逆向递增序列（递减序列），遇到ratings[i] > ratings[i + 1]，则candy[i] = Math.max(candy[i + 1] + 1,candy[i])
1 if(ratings == null) return 0; 2 if(ratings.length < 2) return ratings.length; 3 int[] candy = new int[ratings.length]; 4 int length = ratings.length; 5 candy[0] = 1; 6 for(int i = 1; i < length; i++){ 7 if( ratings[i] > ratings[i - 1]){ 8 candy[i] = candy[i - 1] + 1; 9 }else{10 candy[i] = 1;11 }12 }13 for(int i = length - 2; i >= 0; i--){14 if(ratings[i] > ratings[i + 1]){15 candy[i] = Math.max(candy[i + 1] + 1,candy[i]);16 }17 }18 int res = 0;19 for(int i = 0; i < length; res+= candy[i++]);20 return res;21
优化，单边扫描，双指针，扫描过程中找到严格递增和递减序列，递增序列则根据个数，将candy从1开始逐个增加，
递减序列需要注意：首先根据元素个数，逆向从1逐个增加。遇到最大值，则同样candy[i] = Math.max(candy[i + 1] + 1,candy[i]);
实现起来，代码略麻烦.....下次见。。。。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。