首页 > 其他 > 详细

leetcode--Candy

时间:2014-06-22 13:16:52      阅读:312      评论:0      收藏:0      [点我收藏+]

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;    
    }
}

  

leetcode--Candy,布布扣,bubuko.com

leetcode--Candy

原文:http://www.cnblogs.com/averillzheng/p/3801659.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!