Candy
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?
左右各遍历一次，依据前一个位置的candy数计算当前位置需要的最小candy数
由于两次遍历的结果都要满足，因此对同一位置取max即可。
class Solution { public: int candy(vector<int> &ratings) { if(ratings.empty()) return 0; vector<int>::size_type size = ratings.size(); vector<int> candies(size, 1); //from left to right for(vector<int>::size_type st = 1; st < size; st ++) { if(ratings[st] > ratings[st-1]) candies[st] = candies[st-1]+1; //else if(ratings[st] < ratings[st-1]) // candies[st] = 1; //else // candies[st] = 1; } //from right to left int Sum = candies[size-1]; for(int st = size-2; st >= 0; st --) {//attention!!! if st is unsigned int, it will out of range if(ratings[st] > ratings[st+1]) candies[st] = max(candies[st], candies[st+1]+1); //else if(ratings[st] < ratings[st+1]) // candies[st] = max(candies[st], 1); //else // candies[st] = max(candies[st], 1); Sum += candies[st]; } return Sum; } };
原文：http://www.cnblogs.com/ganganloveu/p/4115571.html