首页 > 代码库 > Candy

Candy

地址:https://oj.leetcode.com/problems/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?

其实最终就是需要满足高的rating比他邻居获得更多糖果。最简单办法就是先从头到尾设置一次糖果分配数,如果比前面一个rating 高则分糖果数加1,如果不高则先赋值1。然后从尾到头再次遍历一次,从而使得高rating必然获得比邻居更多的糖果。

public class Solution {	public int candy(int[] ratings) {		if(ratings.length == 0){			return 0;		}		// 算法思想:从头到尾遍历数组,如果满足rating 更大 就给A[i-1]+1个,如果小就先赋值1.		int []A = new int[ratings.length];		A[0] = 1;		for(int i=1;i<ratings.length;i++){			if(ratings[i]>ratings[i-1]){				A[i]= A[i-1]+1;			}else {				A[i] = 1;			}		}		int ans = A[ratings.length-1];		// 从尾到头再遍历一次,两次遍历过后就满足更高rating 有用更多糖果。		for(int i=ratings.length-2;i>=0;i--){			if(ratings[i]>ratings[i+1]){				A[i] = Math.max(A[i], A[i+1]+1);			}			ans+= A[i];		}		return ans;	}}


 

Candy