题目描述
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)每个小孩至少一颗糖
2)评分高的小孩发的糖比他旁边两个小孩的多
因此最少需要多少糖果才够分？
解题思路：
遍历两边，首先每个人得一块糖，第一遍从左到右，若当前点比前一个点高就比前者多一块。
这样保证了在一个方向上满足了要求。第二遍从右往左，若左右两点，左侧高于右侧，但
左侧的糖果数不多于右侧，则左侧糖果数等于右侧糖果数+1，这就保证了另一个方向上满足要求。
最后将各个位置的糖果数累加起来就可以了。
代码实现：
class Solution {
public:
int candy(vector<int> &ratings) {
int n=ratings.size();
//candy set
vector<int>Candy(n,);
//from left to right
for(int i();i<n-;i++){
if(ratings[i+]>ratings[i])
Candy[i+]=Candy[i]+;
}
//from right to left
for(int j=n-;j>;j--){
if(ratings[j-]>ratings[j]&&Candy[j-]<=Candy[j])
Candy[j-]=Candy[j]+;
}
//add all
int sum();
for(auto a:Candy)
sum+=a;
return sum;
}
};