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?

Two passes:

  • left to right, if a[i] > a[i-1], increase the candy of i by 1, if not set it as 1.
  • right to left, if a[i-1] > a[i], BUT count is less, then increase candy of i.
public class Solution {
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length == 0) return 0;
        int[] count = new int[ratings.length];
        count[0] = 1;
        for(int i=1;i<ratings.length;i++){
            if(ratings[i] > ratings[i-1]){
                count[i] = count[i-1] + 1;
            }else{
                count[i] = 1;
            }
        }
        int res = count[ratings.length-1];

        for(int i=ratings.length-1; i >0;i--){
            if(ratings[i-1] > ratings[i] && count[i-1] <= count[i]){
                count[i-1] = count[i] + 1;
            }
            res += count[i-1];
        }

        return res;

    }
}

results matching ""

    No results matching ""