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?
题目的意思：
有N个孩子站成一条线，每个孩子分配一个排名。你将要给这些孩子一些糖果，要求：
- 每个孩子必须至少有一个糖果
- 孩子如果有个高排名，将得到糖果比其邻居的多
解题思路是：
（1）由于每个小孩至少有一个糖果，故将每个小孩的初始糖果初始化为1
（2）从前往后扫描，如果第i个小孩排名比第i-1高，那么第i个小孩的糖果数目+1
（3）从后往前扫描，如果第i个小孩排名比第i+1高，那么第i个小孩的糖果数目=max(第i个小孩的糖果数目，第i+1个小孩的糖果数目+1)
（4）最后将所有小孩的糖果数目累积即可
class Solution {
public:
int candy(vector<int> &ratings) {
vector<int> candy(ratings.size(),);
for(int i = ; i < ratings.size(); ++ i){
if(ratings[i]>ratings[i-]) candy[i]=candy[i-]+;
}
for(int i = ratings.size()-; i>=; -- i){
if(ratings[i] > ratings[i+]) candy[i] = max(candy[i+]+,candy[i]);
}
return accumulate(candy.begin(),candy.end(),);
}
};
关于此题目类似的题目
在一维数组中，找出一个点，使得其所有左边的数字均小于等于它，所有右边的数字都大于等于它。要求在线性时间内返回这个点所在的下标。
如A={1，0，1，0，1，2，3}，返回下标4或5
解题思路与上面类似
首先，从左到右扫描一遍数组，通过一个辅助布尔数组记录哪些大于等于其之前所有元素的元素；
其次，从右到左扫描一遍数组，如果其后所有元素大于等于当前元素，而且在第一个遍历时当前元素大于等于之前的所有元素，则程序返回下标；
int getMagnitutePole(vector<int> A){
if(A.size() == ) return ;
vector<bool> flag(A.size(), false);
int curMax = A[];
for(int i = ; i < A.size(); ++ i){
if(A[i]>=curMax){
curMax = A[i];
flag[i] = true;
}
}
int curMin = A[A.size()-];
for(int i = A.size()-; i >=; -- i ){
if(A[i] <= curMin){
curMin = A[i];
if(flag[i]) return i;
}
}
return -;
}