题目:
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?
有N个孩子站在一排。为每个孩子分配一个评等值。
你给这些孩子提供糖果,这些孩子必须有以下条件:
每个孩子必须至少有一个糖果。评分高的孩子比邻居得到更多的糖果。
你必须给多少最低限度的糖果?
思路:
- 思路一:
若用动态规划:
- 根据限制我们可以想到一个二维数组,从初次扫描开始,每次扫描将评估值与同行前一个结点和前一行后一个结点的值比较,如果大于就加一。
- 何时结束:N个值,最多进行N次循环,因为最多N个不同的数,最大糖果差为N。
本题,使用N * N的数组会超出内存限制,于是改用2 * N的数组,其实,也只用到两行,前一行,后一行。
- 思路二:
第一遍从左向右扫描保证比左边邻居大1
第二遍从右向左扫描保证比右边邻居大1
import java.util.*;
public class Solution {
public int candy(int[] ratings) {
if(ratings.length == 0)
return 0;
if(ratings.length == 1)
return 1;
int[] candy = new int[ratings.length];
Arrays.fill(candy, 1);
int sum = 0;
for(int i = 0; i < ratings.length - 1; i++)
if(ratings[i] < ratings[i + 1])
candy[i + 1] = candy[i] + 1;
for(int i = ratings.length - 1; i > 0; i--){
sum += candy[i];
if(ratings[i] < ratings[i - 1] && candy[i] >= candy[i-1])
candy[i-1] = candy[i] + 1;
}
sum += candy[0];
return sum;
}
}
网友评论