Description
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?
简单来说就是每个小孩都有自己不同的权值,如果这个小孩的权值比左右两个的小孩大,它就需要拿更多的权值
解题思路
Solution.1 优先队列
我开始想到的是优先队列的方法,优先pop出来的是权值最小的孩子,注意这里不能用大根堆,用大根堆的方法是错的,因为你无法确定第一个pop出来的小孩应该赋予多少个candy。 所以我们需要从权值最小的小孩开始,并赋予为1,同时我们需要维护一个vector,用于记录pop出的小孩赋予了多少个candy,以便确定下一个pop出的等于附近小孩的candy+1(相同则取相同即可)。这种方法的时间复杂度为2O(n),空间复杂度也为2O(n),所以总的来说不是最优的算法,只beat 15%
struct compare{
bool operator()(const pair<int,int> &p1,const pair<int,int> &p2){
return p1.first>p2.first;
}
};
class Solution {
public:
int candy(vector<int>& ratings) {
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
int size = ratings.size(),count = size;
vector<int> candy(size,0);
for(int i=0;i<size;++i){
pq.push(make_pair(ratings[i],i));
}
while(!pq.empty()){//从小到大 pop,因为从大到小好像有问题
pair<int,int> tmp = pq.top();
//cout<<tmp.first<<" "<<tmp.second<<endl;
//3种情况,1,比两端都小跳过,比一端大,比两端都大
int left = tmp.second-1,right = tmp.second +1;
if((left<0||ratings[left]>=tmp.first)&&(right>=size||ratings[right]>=tmp.first)){
pq.pop();
continue;
}
else if((left>=0&&ratings[left]<tmp.first)&&(right>=size||ratings[right]>=tmp.first)){
candy[tmp.second] = candy[left] + 1;
count += candy[tmp.second];
}
else if((left<0||ratings[left]>=tmp.first)&&(right<size&&ratings[right]<tmp.first)){
candy[tmp.second] = candy[right] + 1;
count += candy[tmp.second];
}
else{
int neibor = left<0?candy[right]:right>=size?candy[left]:max(candy[left],candy[right]);
candy[tmp.second] = neibor +1;
count += candy[tmp.second];
}
/*for(auto c:candy)
cout<<c<<" ";*/
pq.pop();
}
return count;
}
};
Solution2 不用优先队列,只用记录Candy的vector
我们能不能不用优先队列呢,答案是可以的,思路就是我们可以从左到右遍历数组做一次贪心,再从右到左做一次贪心(逆序对),注意第二次遍历的时候需要做一点判断
- 我们做正向遍历的时候,如果ratings[i]>rating[i-1],candy[i] = candy[i-1]+1,否则为1
- 逆向遍历的时候,我们需要加上判断candy[i]<=candy[i+1],因为在正向遍历的时候,可能candy[i]就已经是>candy[i+1]了 经过两遍遍历后就能得到结果
class Solution { public: int candy(vector<int>& ratings) { int size = ratings.size(); vector<int> candy(size,0); candy[0] = 1; for(int i=1;i<size;++i){ candy[i] = (ratings[i]>ratings[i-1]?candy[i-1]+1:1); } int count = candy[size-1]; for(int i=size-2;i>=0;--i){ count += (candy[i] = ratings[i]>ratings[i+1]&&candy[i]<=candy[i+1]?candy[i+1]+1:candy[i]); } /* for(auto i:candy) cout<<i<<" ";*/ return count; } };
Solution3 一遍遍历
需要两遍遍历的原因主要在于在正向遍历时没有处理好逆序数的情况。如果在正向遍历也能处理逆序数的化,一遍遍历即可得到满足,所以,我们需要记录连续出现逆序数的个数这里用dropCount表示,当出现ratings[i]>=ratings[i-1]时,逆序对结束,如果这时候dropCount>0,我们就需要处理逆序对的情况,很简单,等差数列嘛,但是还需要注意一种情况,补firstdrop个数(因为这种方法并没有记录每个学生candy),相当于只记录总数 考虑下面一种情况[1,3,7,6,5,4,3,2,1],顺序遍历时,7只为3个candy,但我们在记录逆序数时,7至少为7个 candy,所以我们在dropCount处理完后还需要加上 整个算法的时间复杂度为O(n),且空间复杂度为O(1),算是最高效的一种方法
preCandy = (ratings[i]==ratings[i-1]?1:preCandy+1);
count += preCandy;
class Solution {
public:
int candy(vector<int>& ratings) {
int size = ratings.size();
int preCandy = 1,dropCount=0,count = 1;
for(int i=1;i<size;++i){
if(ratings[i]>=ratings[i-1]){//注意判断是大于等于
if(dropCount>0){
count += ((dropCount+1)*dropCount)>>1;
if(dropCount>=preCandy)
count += dropCount - preCandy +1;
dropCount = 0;
preCandy = 1;
}
/**
* 这段是用于计算当前递增的candy
*/
preCandy = (ratings[i]==ratings[i-1]?1:preCandy+1);
count += preCandy;
}
else
++dropCount;
}
///当到最后仍然还是降序的序列时
if(dropCount>0){
count += ((dropCount+1)*dropCount)>>1;
if(dropCount>=preCandy)
count += dropCount - preCandy +1;
}
return count;
}
};