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:
What is the minimum candies you must give?
public class Solution { public int candy(int[] ratings) { if(ratings.length == 0) return 0; int[] num = new int[ratings.length]; for(int i = 0; i < ratings.length ; i++){ num[i] = 1; } for(int i = 1 ; i < ratings.length ; i++){ if( ratings[i-1] < ratings[i]){ num[i] = num[i-1] + 1; } } for(int i = ratings.length-2 ; i >= 0 ; i--){ if( ratings[i] > ratings[i+1] ){ int tmp = num[i+1]+1; if(tmp>num[i]) num[i]=tmp; } } int sum = 0; for(int i = 0; i < ratings.length ; i++){ sum += num[i]; } return sum; } }
learned: scan linearly from start to end; then scan from end again to check if num[i+1]+1 > num[i]