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:
What is the minimum candies you must give?
思路：neighbor=>元素值与前、后元素有关=>前向、后向两次扫描。
class Solution { public: int candy(vector<int> &ratings) { vector<int> new_ratings(ratings.size(), 1); for(int i = 1; i < ratings.size(); i++) //for the first time, scan from beginning { if(ratings[i] > ratings[i-1]) { new_ratings[i] = new_ratings[i-1]+1; } } for(int i=ratings.size()-2;i>=0;i--){ //for the second time, scan from the end if(ratings[i]>ratings[i+1]&&new_ratings[i]<=new_ratings[i+1]){ new_ratings[i]=new_ratings[i+1]+1; } } int sum=0; for(int i=0;i<new_ratings.size();i++){ sum+=new_ratings[i]; } return sum; } };
原文：http://www.cnblogs.com/qionglouyuyu/p/4853463.html