题目描述:(链接)
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?
解题思路：
开辟一个数组记录每个孩子的糖果数，前后两次扫描该数组，改变当前孩子的糖果数目。
1 class Solution { 2 public: 3 int candy(vector<int>& ratings) { 4 int n = ratings.size(); 5 vector<int> result(n); 6 7 for (int i = 1; i < n; ++i) { 8 if (ratings[i] > ratings[i - 1]) { 9 result[i] = result[i - 1] + 1; 10 } 11 } 12 13 for (int i = n - 2; i >= 0; --i) { 14 if (ratings[i] > ratings[i + 1]) { 15 result[i] = (result[i + 1] + 1 > result[i])? result[i + 1] + 1 : result[i]; 16 } 17 } 18 19 int sum = 0; 20 for (int i = 0; i < n; ++i) { 21 sum += result[i]; 22 } 23 24 return sum + n; 25 } 26 };
原文：http://www.cnblogs.com/skycore/p/4888646.html