135. Candy Leetcode Java

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?

Solution:

Two rounds correction.

1st round from left to right, and only consider left neighbor.  If the left neighbor has higher rating, set candy of current child as 1, otherwise set as one more candy as its left neighbor's candies. 

2nd round from right to left, and only consider right neighbor. Correct those who has less or equal candies with higher rating than its right neighbor.

For 1st round, it will make sure all the children with higher rating than its left neighbor will get more candies. And it is the minimum distribution method, because we only give 1 extra. For 2nd round, it will make sure all the children with higher rating than its right neighbor will get more candies. Because we only increase the candy numbers in this round, it will satisfy the conditions for both neighbors. 
Time complexity: O(n)

  public int candy(int[] ratings) {  
    if(ratings==null || ratings.length==0) return 0;  
    int[] candies= new int[ratings.length];  
    candies[0]=1;  
    for(int i=1;i<ratings.length;i++){  
      if(ratings[i]>ratings[i-1]) candies[i]=candies[i-1]+1;  
      else candies[i]=1;  
    }  
    int sum=candies[ratings.length-1];  
    for(int i=ratings.length-2;i>=0;i--){  
      if(ratings[i]>ratings[i+1]){  
        candies[i]=Math.max(candies[i+1]+1,candies[i]);  
      }  
      sum+=candies[i];  
    }  
    return sum;  
   }