题意
有n个小孩站成一条线，每个小孩都有一个正整数评分，所以可以把小孩们的评分记成一个正整数array ratings。
我们基于以下两个原则给小孩发糖果
- 每个小孩至少要有一个糖果
- 当当前小孩的评分大于他其中一个邻居时，我们就多给这个小孩分配一个糖果
问： 最少要用多少个糖果满足给定的 ratings 数组？
输入输出举例
解法一
方法思路
把所有孩子的糖果数初始化为1； 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加1。
通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。
在样例 ratings=[1,0,2]中，我们初始化糖果分配为[1,1,1]，第一次遍历更新后的结果为[1,1,2]，第二次遍历更新后的结果为[2,1,2]。
代码
public int getCandies(int[] ratings) {
if (ratings.length <= 1) {
return 1;
}
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
//从左往右扫描，如果右边的rating大于左边的则右边孩子的糖果数等于左边孩子的糖果数+1
for (int i = 0; i + 1 < candies.length; i++) {
if (ratings[i] < ratings[i+1]) {
candies[i+1] = candies[i] + 1;
}
}
int count = candies[candies.length - 1]; // store the number of the least candies needed
//从右往左扫描，如果左边的rating大于右边的，且左边的糖果数<=右边孩子的糖果数，则左边孩子的糖果数等于右边孩子的糖果数+1
for (int j = candies.length - 1; j - 1 >= 0; j--) {
if (ratings[j-1] > ratings[j] && candies[j-1] <= candies[j]) {
candies[j-1] = candies[j] + 1;
}
count += candies[j-1];
}
return count;
}
复杂度
Time: O(n) two traversals of the candies array
Space: O(n) open a new array of size n for candies
解法二
方法思路
运用到数学原理–等差数列 arithmetic sequence
我们先给第一个小孩1个糖果，那么接下来的那个小孩有三种情况：
- 他的rating > 第一个小孩的，给他 （第一个同学的糖果数 + 1）
- 他的rating = 第一个小孩的，给他 1个糖果
- 他的rating < 第一个小孩的, 这时候我们不知道要给他多少糖果，因为后面可能还有rating比他更低的小孩
对第3种情况，举个例子：
ratings = [6, 3, 1]
首先给第一个rating为6的小孩1个糖果，然后指针走到第二个小孩，发现啊哦，他的rating比第一个小孩来的小。这时候别担心，我们虽然先补给他糖果，但是我们用一个count变量记录这是等差数列的开始（其实等差数列开始于第一个小孩，但为了方便，我们就把第一个小孩记作pre，把第二个小孩算作等差数列的开始，之后会处理pre的）。
然后再往下看第三个小孩的rating小于第二个小孩，那么他就是等差数列的第二个项，count加1变为2。再往下看，没有第四个小孩了。
那么，第二个小孩和第三个小孩组成的等差数列，一共要给她们几个糖果呢？
这就是用到等差数列求和 (首项+末项)*项数/2 即 (2 + 1) * 2 / 2 = 3个糖果果。
OK，然后再回头处理第一个小孩pre的情况。已知pre已经有一个糖果了。
我们要返回他 count - pre + 1 = 2 - 1 + 1 = 2个糖果。<– 把这返还他的糖果加到总糖果数目里面去，我们就得到 1 【初始的】 + 3 【等差求和的】 + 2 【返还pre的】= 6个糖果。
这里面还有一些细节，我就先不展开，大家可以根据下面代码进行分析。
代码
public int getCandies(int[] ratings) {
if (ratings.length <= 1) {
return 1;
}
int res = 1, pre = 1, count = 0; // res存结果, pre为发现ratings等差数列出现时的前一个孩子的糖果计数 初始为1，count记录等差数列的项数
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] >= ratings[i-1]) {
if (count > 0) {
res += count * (count + 1) / 2; //等差数列求和
if (count >= pre) {
res += count - pre + 1; //count - pre + 1 为初次算给pre的糖果数
}
count = 0; //还原
pre = 1;
}
pre = (ratings[i] == ratings[i-1]) ? 1 : pre + 1; // 再次看pre要不要在原来基础上追加一个糖果
res += pre;
} else {
count++; // 等差数列开始出现
}
}
if (count > 0) {
res += count * (count + 1) / 2;
if (count >= pre) {
res += count - pre + 1;
}
}
return res;
}
复杂度
Time: O(n) one traversals of the candies array
Space: O(1) just opens 3 new int vars
总结
一般面试能答到解法一的贪心算法，应该就OK了。除非是面谷歌这样难度的公司，可能会要求想到解法二的一遍遍历的方法。这样对面试者的活学活用数学知识的水平有一定考验。