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?
我一开始的思路是：
首先，将ratings数组按rating的值进行排序分层，做成一个multimap，每个rating作为key，value是对应的所有数组下标，用一个list封装。
之后，再根据rating的值从低到高给各个孩子分配最少的糖果数，初始值为1，并且保证如果该孩子的rating比其邻居的高，则必须比邻居的糖果数要多1。
因为要实现对rating的排序分层，我使用了TreeMap。
public int candy(int[] ratings) {
if (ratings.length == 0) return 0;
int[] candies = new int[ratings.length];
int count = 0;
// Key: rating value; Value: all the corresponding child indices
TreeMap<Integer, ArrayList<Integer>> tm = new TreeMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < ratings.length; i++) {
if (!tm.containsKey(ratings[i])) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(i);
tm.put(ratings[i], list);
} else {
ArrayList<Integer> list = tm.get(ratings[i]);
list.add(i);
}
}
// traverse the tree map by the rating level
Set<Integer> set = tm.keySet();
for (int rating : set) {
ArrayList<Integer> list = tm.get(rating);
for (int index : list) {
candies[index] = 1;
// check if the candies are more than the left neighbor
if (index - 1 > 0 && ratings[index] > ratings[index - 1]
&& candies[index] <= candies[index - 1]) {
candies[index] = candies[index - 1] + 1;
}
// check if the candies are more than the right neighbor
if (index + 1 < ratings.length
&& ratings[index] > ratings[index + 1]
&& candies[index] <= candies[index + 1]) {
candies[index] = candies[index + 1] + 1;
}
count += candies[index];
}
}
return count;
}
按照这样的思路，总共需要遍历原来rating数组一次来构造TreeMap，然后再遍历一次TreeMap，计算分配给每个孩子的糖果数，并计算其总数。总共两轮遍历，感觉时间复杂度应该是O(N)，可是为什么结果还是超时？
琢磨了一段时间，发现TreeMap由于具有排序时间，并不像HashMap那样具有O(1)的插入时间，而是像其他具有排序性质的数据结构一样，需要O(lgN)的时间才能完成插入操作。所以，这个实现的性能瓶颈在于构造TreeMap，一共需要O(N*lgN)的时间。
所以得另外转换思路了。网上有一种巧妙的解法，只需要两次对数组进行两次扫描。
1）从左往右扫描，如果某个孩子的糖果数少于rating低的左邻居，那么就让他持有比左邻居多1的糖果数。
2）从右往左扫描，如果某个孩子的糖果数少于rating低的优邻居，那么就让他持有比右邻居多1的糖果数。
然后对数组求和即可。
public int candy(int[] ratings) {
if (ratings.length == 0)
return 0;
int[] candies = new int[ratings.length];
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1])
candies[i] = candies[i - 1] + 1;
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1])
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
int ret = ratings.length;
for (int i : candies) {
ret += i;
}
return ret;
}
当然，这里最后一步求和其实不需要另外扫描一遍数组，完全可以跟第二次扫描合并。
另外网上还发现了一种有趣的一维DP解法：
1）如果比前一个孩子rating高，必须比前一个孩子多给1个糖；
2）如果跟前一个孩子rating相同，给一个糖就可以了（并不需要跟前一个孩子所持糖果数相等）；
3）如果比前一个孩子rating低，给一个糖，然后再多给前面孩子一个糖。另外，还有继续一直检查是否需要多给更前面的孩子一个糖，直到遇到情况1或情况2。
public int candy(int[] ratings) {
if (ratings.length == 0)
return 0;
int[] d = new int[ratings.length];
d[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] == ratings[i - 1])
d[i] = 1;
else if (ratings[i] > ratings[i - 1])
d[i] = d[i - 1] + 1;
else {// should give less candies than the previous child
d[i] = 1;
if (d[i - 1] == 1) {
int j = i;
while (j > 0 && ratings[j - 1] > ratings[j]
&& d[j - 1] == d[j]) {
// only push backwards when the ratings are different
// but the # of candies are the same
d[j - 1]++;
j--;
}
}
}
}
int sum = 0;
for (int i = 0; i < ratings.length; i++) {
sum += d[i];
}
return sum;
}