LeetCode-Candy

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?

##解题思路
该题与Trapping Rain Water非常类似，都是要求的变量跟左右元素有关系的题目。因此可以分别从两边对其进行遍历。在该题中，我们首先从左边遍历得到每个孩子在左边所需要的最少糖果，然后再从右边遍历得到每个孩子在右边所需要的最少糖果，最终该孩子所需的最少糖果为左边和右边中的最大的那个才能满足要求。

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public int candy(int[] ratings) {
        //由于一个孩子的糖果数与左右孩子都有关系，因此需要分别从两边进行遍历
        //首先得到左边的最少需要糖果数，然后从右开始遍历
    	if(ratings==null || ratings.length==0)
    		return 0;
    	//定义左边每个孩子最少需要的糖果数
    	int[] left=new int[ratings.length];
    	left[0]=1;
    	for(int i=1;i<ratings.length;i++)
    	{
    		if(ratings[i]>ratings[i-1])
    			left[i]=left[i-1]+1;
    		else
    			left[i]=1;
    	}

    	//定义右边每个孩子最少需要的糖果数
    	int[] right=new int[ratings.length];
    	right[ratings.length-1]=1;
    	for(int i=ratings.length-2;i>=0;i--)
    	{
    		if(ratings[i]>ratings[i+1])
    			right[i]=right[i+1]+1;
    		else
    			right[i]=1;
    	}
    	//定义每个孩子的最少所需糖果数
    	int res=0;
    	for(int i=0;i<ratings.length;i++)
    	{
    		res=Math.max(left[i],right[i])+res;
    	}
    	return res;

    }
}

Comments

▲