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?
题目解析：
本以为“等级”高的分配的个数一定比等级低的高。如果是这样的话，排序后，就很容易计算。
但是题目不是这个意思，是等级高的比相邻的等级低的分配的个数多。比如1,2,2 分配的个数是1-2-1。一共四个。这样的话就麻烦了。得好好研究序列找到规律。
方案一：
通过举例是个很好的研究方法。比如1,2,3,3,4 分配个数为1-2-3-1-2。递增的话就依次增加，如果碰到当前值比前一个小的或相等的，就变为1。但又出现一个问题，比如1,2,3,4,5,4,3,2 分配个数为1-2-3-4-5-3-2-1。我们该怎么去考虑？可以这样碰到arr[4] = 5后面的arr[5] = 4以后，先给4分配1个即num[5]=1，再往后遍历，碰到arr[6] = 3比arr[5] = 4还小，就给3赋值为1即num[6]，然后对num[6...0]数据进行修正(arr[i]>arr[i+1]
&& num[i]<=num[i+1] ======> num[i] = num[i+1]+1)。
这种时间复杂度为O(n^2)比较高。
class Solution {
public:
int candy(vector<int> &ratings) {
int len = ratings.size();
int *num = new int[len];
if(len == 0)
return 0;
num[0] = 1;
for(int i = 0;i < len;i++){
if(ratings[i]>ratings[i-1])
num[i] = num[i-1]+1;
else{
num[i] = 1;
Ajust(ratings,i,num);
}
}
int sum = 0;
for(int i = 0;i < len;i++)
sum += num[i];
return sum;
}
void Ajust(vector<int> &ratings,int index,int *num){
for(int i = index-1;i>=0;i--){
if(ratings[i]>ratings[i+1] && num[i]<=num[i+1]){
num[i] = num[i+1]+1;
}else
break;
}
}
};
方案二：
如果我们第一趟走的时候，直接将arr[i]<=arr[i-1]时，num[i]=1。先不处理，然后反向遍历，进行一趟修正。这样时间复杂度就降为O(n)。其修正过程和上面的是一样的(arr[i]>arr[i+1] && num[i]<=num[i+1] ======> num[i] = num[i+1]+1)。
class Solution {
public:
int candy(vector<int> &ratings) {
int len = ratings.size();
int *num = new int[len];
if(len == 0)
return 0;
num[0] = 1;
for(int i = 0;i < len;i++){
if(ratings[i]>ratings[i-1])
num[i] = num[i-1]+1;
else
num[i] = 1;
}
Ajust(ratings,num);
int sum = 0;
for(int i = 0;i < len;i++){
sum += num[i];
}
return sum;
}
void Ajust(vector<int> &ratings,int *num){
for(int i = ratings.size()-2;i>=0;i--){
if(ratings[i]>ratings[i+1] && num[i]<=num[i+1]){
num[i] = num[i+1]+1;
}
}
}
};
方案三：
方案二已经很完美了，时间复杂度已经降到最低，但是空间复杂度为O(n)。能否将空间复杂度也降下来？
其实方案二中已经隐隐约约感觉到，当连续递增或递减的时候，分配的数据是：1、2、3、4....或...4、3、2、1。这些都是连续的，那么我们可以统计连续严格递增的个数，连续严格递减的个数n，然后n(n+1)/2。但是中间过度点要额外考察，比如：（1、2、5、4、3、2、1）这个5放在递增序列中为3，放在递减序列中为5。这就造成了差别。
不过网页有个好的方法，不过没用我给的公式。记录下递减开始前一个孩子要给的糖果数k，然后遍历记录递减序列的长度len，如果len>k+1，那么以后再遍历len还继续增加的话，增加新分配孩子的糖果数的同时，要额外加上1，代表递减开始的元素起先分配的值小了。
而对于递减序列，我们不必严格按照“等级高的比等级低的分配的多”，我们只是为了计算个数，那么“递减开始的第二个孩子”分配1个，第三个孩子分配两个。
int candy(vector<int> &ratings) {
int Total = 0; /// Total candies
int length = 0; /// Continuous descending length of rate
int nPreCanCnt = 1; /// Previous child's candy count
int beforeDenc = nPreCanCnt;
if(ratings.begin() != ratings.end())
{
Total++; //Counting the first child's candy (1).
for(vector<int>::iterator i = ratings.begin()+1; i!= ratings.end(); i++)
{
if(*i < *(i-1))
{
length++;
if(beforeDenc <= length)
{
Total++;
}
Total += length;
nPreCanCnt = 1; //This step is important, it ensures that once we leave the decending sequence, candy number start from 1
}
else
{
int curCanCnt = 0;
if(*i > *(i-1))
{
curCanCnt = (nPreCanCnt + 1);
}
else
{
curCanCnt = 1;
}
Total += curCanCnt;
nPreCanCnt = curCanCnt;
length = 0; //reset length of decending sequence
beforeDenc = curCanCnt;
}
}
}
return Total;
}