首页 > 代码库 > 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?
public class Solution { /**This algorithm need O(n) time.<br> *@author Averill Zheng *@version 2014-06-21 *@since JDK 1.7 */ public int candy(int[] ratings) { int length = ratings.length, temp = 1, max = 0; boolean decrease = true; int total = 0; if(length > 0){ total = 1; for(int i = 1 ; i < length; ++i){ if(ratings[i] > ratings[i - 1]){ if(decrease){ temp = 1; decrease = false; } total +=(++temp); max = temp; } else if(ratings[i] < ratings[i - 1]){ if(!decrease){ temp = 0; decrease = true; } total +=(++temp); if(max > 0 && temp >= max){ total += (++temp - max); max = 0; } } else{ decrease = true; total += 1; max = 0; temp = 1; } } } return total; }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。