Question
Formatted question description: https://leetcode.ca/all/135.html
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?
Algorithm
First initialize one candy for each person, and then the algorithm needs to traverse twice
- the first traverse from left to right, if the level of the small pot on the right is high, one more candy to be added, which ensures that there are more candies in left-to-right direction.
- Then it traverses from right to left again. If the two adjacent left sides have a higher level and the left side has fewer candies, the number of candies on the left is the number of candies on the right plus one. Finally, add up the number of candies of all the friends
My idea is to use four test cases: ratings:
- Monotonous increase: 7,8,9
- Monotonic reduction: 9,8,7
- Wave shape: 7,8,9,8,7
- Wave trough shape: 9,8,7,8,9
Code
Java
public class Candy {
public class Solution {
public int candy(int[] ratings) {
int sum = 0;
if (ratings == null || ratings.length == 0) {
return sum;
}
int[] candies = new int[ratings.length];
// scan from left, and then scan from right
for (int i = 1; i < ratings.length; i++) {
// start from 2nd element
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i] < candies[i - 1] + 1 ? candies[i - 1] + 1 : candies[i];
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
// also, start from 2nd last
if (ratings[i] > ratings[i + 1]) {
candies[i] = candies[i] < candies[i + 1] + 1 ? candies[i + 1] + 1 : candies[i];
}
}
for (int each: candies) {
sum += each;
}
return sum + ratings.length; // at least one candy for each
}
}
}