题意
给每个孩子分糖果，如果这个孩子的rating比相邻的孩子高，那么他分到的糖果就要比他多，求最少需要多少糖果。
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.
test cases
[3,2,1,1,2,4,3,2,1,0,0]
[1,0,2]
[1,0,2,2,3,4,5,6,7,7,8,9,0,1,2,3,2,1,1,2,1,0]
[3,2,1,1,2,3,2,2,3,4,2,2,1]
[]
[1,2,2,2,1,1,3,1,2,10,20,19,18,17,16,15,4,3,2,1,2,2,1,1,0,1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1,0,10]
[1]
[0]
解1 只遍历一遍即得出结果
时间复杂度O(N)
[3,2,1,1,2,4,3,2,1,0,0]对这个用例，分法应该为：
[3,2,1,1,2,5,4,3,2,1,1]
过程为：
[1]
[2,1]
[3,2,1]
[3,2,1,1]
[3,2,1,1,2]
[3,2,1,1,2,3]
[3,2,1,1,2,3,1]
[3,2,1,1,2,3,2,1]
[3,2,1,1,2,4,3,2,1]
[3,2,1,1,2,5,4,3,2,1]
[3,2,1,1,2,5,4,3,2,1,1]
思路：维护3个变量：当前高度、前最大高度、当前台阶高度。
如果比前一个孩子分高，
如果是第一次上升，那么当前台阶高度=2，
如果不是第一次上升，那么当前台阶高度++；
结果加上当前台阶高度。
如果比前一个孩子分低，
如果不是第一次下降，那么台阶高度++；
如果是第一次下降，那么台阶高度=1；
结果加上 high < maxHigh ? high : maxHigh + 1;
如果相等，
与前面隔断。
讲不清楚，也很复杂，直接上代码
// Runtime: 2 ms, faster than 95.29% of Java online submissions for Candy.
//Memory Usage: 39.7 MB, less than 16.42% of Java online submissions for Candy.
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0)
return 0;
int prev = ratings[0];
int sum = 1;
int level = 1;
int high = 1;
int maxHigh = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > prev) {
if (level++ == 1)
high = 2;
else
high++;
maxHigh = high;
sum += level;
} else if (ratings[i] < prev) {
if (level == 1) {
high++;
} else {
level = 1;
high = 1;
}
sum += high < maxHigh ? high : maxHigh + 1;
if (high == maxHigh)
high++;
maxHigh = Math.max(high, maxHigh);
} else {
level = 1;
high = 1;
maxHigh = 1;
sum += 1;
}
prev = ratings[i];
}
return sum;
}
解2
因为有排序，时间复杂度O(NlogN(N))
贪心，思路就比较简单了，实现也简单，只是效率低一些。
永远找出分数最小的一个，如果比邻居高，那么糖果就要比高的邻居还要高，并且取最大值，分配。
根据这个思路，我很快就实现了，结果花费了20ms，花费了解1十倍的时间。
// 贪心
// Runtime: 20 ms, faster than 11.77% of Java online submissions for Candy.
//Memory Usage: 45.7 MB, less than 16.42% of Java online submissions for Candy.
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0)
return 0;
Map<Integer, List<Integer>> indexes = new HashMap<>();
int[] candies = new int[ratings.length];
for (int i = 0; i < ratings.length; i++) {
indexes.putIfAbsent(ratings[i], new ArrayList<>());
indexes.get(ratings[i]).add(i);
}
int[] sorted = Arrays.copyOf(ratings, ratings.length);
Arrays.sort(sorted);
int sum = 0;
for (int i = 0; i < sorted.length; i++) {
if (i > 0 && sorted[i] == sorted[i - 1])
continue;
for (Integer j : indexes.get(sorted[i])) {
if (j > 0 && ratings[j] > ratings[j - 1])
candies[j] = candies[j - 1] + 1;
if (j < ratings.length - 1 && ratings[j] > ratings[j + 1])
candies[j] = Math.max(candies[j], candies[j + 1] + 1);
if (candies[j] == 0)
candies[j] = 1;
sum += candies[j];
}
}
return sum;
}
解3 遍历两次，从左往右一次，从右往左依一次
时间复杂度O(N)
用两种方法做了之后网上看了别人的解法，发现了这种思路简单，容易实现，而且效率也高的做法。
非常赞，其实刚看到这道题的时候就想到了，但是当时就想着只遍历一次，然后在解1的路上越走越远，好在还是做出来了，但是不如解3的方法。
// Runtime: 1 ms, faster than 100.00% of Java online submissions for Candy.
//Memory Usage: 39.7 MB, less than 16.42% of Java online submissions for Candy.
public int candy3(int[] ratings) {
int[] extraCandies = new int[ratings.length];
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
extraCandies[i] = extraCandies[i - 1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i + 1] < ratings[i])
extraCandies[i] = Math.max(extraCandies[i], extraCandies[i + 1] + 1);
}
int sum = 0;
for (int extraCandy : extraCandies) {
sum += extraCandy;
}
return sum + ratings.length;
}