candy

发表于   |   分类于   |  

135. 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?

思路

先从左向右遍历一遍，右边的比左边的大，不大则设置为1
再从右向左遍历一遍，左边的比右边的大，已经大的不动

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
public class Solution {
    public int candy(int[] ratings) {
        
        int len=ratings.length;
        if(len==1)
            return 1;
        int[] num=new int[len];
        num[0]=1;
        for(int i=1;i<len;i++)
        {
            if(ratings[i]>ratings[i-1])
            {
            	num[i]=num[i-1]+1;    
            }
            else
            {
            	num[i]=1;    
            }
        }
        for(int j=len-2;j>=0;j--)
        {
        	if(ratings[j]>ratings[j+1]&&num[j]<=num[j+1])
            {
                num[j]=num[j+1]+1;
            }
        }
        int sum=0;
        for(int i:num)
        {
         	 sum+=i;  
        }
        return sum;
    }
}