Candy

• leetcode 135
• Hard

Description

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?

Hide Tags: Greedy

Thinking

Same way to solve "trap water".

Java Solution

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if(n == 0) return -1;

        int left[] = new int[n];
        int right[] = new int[n];
        int result = 0;

        left[0] = 1;
        right[n - 1] = 1;

        for(int i = 1; i < n; i++){
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
            else left[i] = 1;

            if(ratings[n - 1 - i] > ratings[n - i]) right[n - 1 - i] = right[n - i] + 1;
            else right[n - 1 - i] = 1;
        }

      for(int i = 0; i < n; i++){
          result += Math.max(right[i], left[i]);
      }

      return result;
    }
}