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?
class Solution { public: //two pass, one from the left, other from the right. the left one find the least number of candy that needed according the the left side //right one find the least number of candy that needed according to the right side. int candy(vector<int>& ratings) { if (ratings.empty()) return 0; if (ratings.size() == 1) return 1; int n = ratings.size(); vector<int> candy(n,1); for(int i=1; i < n; i++){ if (ratings[i] > ratings[i-1]) candy[i] = candy[i-1] + 1; } int total = candy[n-1]; for(int i=n-2; i>=0; i--){ if (ratings[i] > ratings[i+1]) candy[i] = max(candy[i], candy[i+1]+1); total += candy[i]; } return total; } };
原文：http://www.cnblogs.com/sherylwang/p/5831086.html