Candy 412
Question
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
Given ratings = [1, 2], return 3.
Given ratings = [1, 1, 1], return 3.
Given ratings = [1, 2, 2], return 4. ([1,2,1]).
Solution
我的思路:
1) 找到所有的最低点(小于等于左边元素并且小于等于右边元素),给最低点1颗糖果
2) 然后从每个最低点开始,向左右两边上升到最高点,每上升一层多给一颗糖果,两个最低点之间的最高点取给糖果多的那个值
九章答案:
1) 先给所有点1颗糖
2) 从左往右,遇到上升区间,给右边小孩比左边小孩多一颗糖
3) 从右往左,遇到上升区间,若左边小孩的糖小于等于右边小孩的糖,则给左边小孩比右边小孩多一颗糖
代码如下:
public class Solution {
/**
* @param ratings Children's ratings
* @return the minimum candies you must give
*/
public int candy(int[] ratings) {
// Write your code here
if(ratings == null || ratings.length == 0){
return 0;
}
if(ratings.length == 1){
return 1;
}
int[] result = new int[ratings.length];
findValley(ratings, result);
spreadFromValley(ratings, result);
int sum = 0;
for(int i = 0; i < result.length; i++){
sum += result[i];
}
return sum;
}
private void findValley(int[] ratings, int[] result){
for(int i = 0; i < ratings.length; i++){
if(i == 0){
if(ratings[i] <= ratings[i + 1]){
result[i] = 1;
}
continue;
}
if(i == ratings.length - 1){
if(ratings[i] <= ratings[i - 1]){
result[i] = 1;
}
continue;
}
if(ratings[i] <= ratings[i - 1] && ratings[i] <= ratings[i + 1]){
result[i] = 1;
}
}
}
private void spreadFromValley(int[] ratings, int[] result){
for(int i = 0; i < result.length; i++){
if(result[i] != 1){
continue;
}
int left = i - 1;
while(left >= 0 && ratings[left] > ratings[left + 1]){
int value = result[left + 1] + 1;
if(result[left] < value){
result[left] = value;
}
left--;
}
int right = i + 1;
while(right <= result.length - 1 && ratings[right] > ratings[right - 1]){
int value = result[right - 1] + 1;
if(result[right] < value){
result[right] = value;
}
right++;
}
}
}
}
九章答案:
public class Solution {
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0) {
return 0;
}
int[] count = new int[ratings.length];
Arrays.fill(count, 1);
int sum = 0;
for(int i = 1; i < ratings.length; i++) {
if(ratings[i] > ratings[i - 1]) {
count[i] = count[i - 1] + 1;
}
}
for(int i = ratings.length - 1; i >= 1; i--) {
sum += count[i];
if(ratings[i - 1] > ratings[i] && count[i - 1] <= count[i]) { // second round has two conditions
count[i-1] = count[i] + 1;
}
}
sum += count[0];
return sum;
}
}