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?
Example 1:
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Solution:
class Solution {
public int candy(int[] ratings) {
int sum = 0;
int n = ratings.length;
// System.out.println(Arrays.toString(ratings));
int[] candies = new int[n];
Arrays.fill(candies, 1);
boolean meetReq = false;
while (!meetReq) {
meetReq = true;
for (int i = 0; i < n; i ++) {
int currRating = ratings[i];
int prevRating = i == 0 ? Integer.MAX_VALUE : ratings[i - 1];
int nextRating = i == n - 1 ? Integer.MAX_VALUE : ratings[i + 1];
if (currRating > prevRating) {
int prevCandies = i == 0 ? 1 : candies[i - 1];
if (candies[i] <= prevCandies) {
candies[i] = prevCandies + 1;
meetReq = false;
}
}
if (currRating > nextRating) {
int nextCandies = i == n - 1 ? 1 : candies[i + 1];
if (candies[i] <= nextCandies) {
candies[i] = nextCandies + 1;
meetReq = false;
}
}
}
// System.out.println(Arrays.toString(candies));
}
int res = 0;
for (int c : candies) res += c;
return res;
}
}
class Solution {
public int candy(int[] ratings) {
int sum = 0;
int n = ratings.length;
// System.out.println(Arrays.toString(ratings));
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 0; i < n; i ++) {
int currRating = ratings[i];
int prevRating = i == 0 ? Integer.MAX_VALUE : ratings[i - 1];
if (currRating > prevRating) {
int prevCandies = i == 0 ? 1 : candies[i - 1];
if (candies[i] <= prevCandies) {
candies[i] = prevCandies + 1;
}
}
}
for (int i = n - 1; i >= 0; i --) {
int currRating = ratings[i];
int nextRating = i == n - 1 ? Integer.MAX_VALUE : ratings[i + 1];
if (currRating > nextRating) {
int nextCandies = i == n - 1 ? 1 : candies[i + 1];
if (candies[i] <= nextCandies) {
candies[i] = Math.max(candies[i], nextCandies + 1);
}
}
}
// System.out.println(Arrays.toString(candies));
int res = 0;
for (int c : candies) res += c;
return res;
}
}