题目：
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?
思路：
本题的总体策略还是贪心法。我开始的思路是：将小孩子们按照rating的升序进行排序，然后依次分配糖果：如果他的某个邻居或者两个邻居已经分配糖果了并且他的rating不大于他的邻居的rating（不可能小于的），那么分配和他的邻居相同数目的糖果；如果他的rating高于他的某个邻居，那么分配他的邻居糖果数目+1。如果他的邻居尚未分配糖果，则只给分配1个。这个思路是可行的，但是代码复杂，时间复杂度为O(nlogn)，空间复杂度O(n)。
采用两边扫描的方法可以将时间复杂度降为O(n)。具体方法如下：先从左往右扫描一遍，如果后面一个比前面大，那么他分配的就多一颗糖果，否则就是1。但是这样会产生一个情况，就是两个相邻的排名一样，那么后一个还是分一个，但是右面的小孩的rating可能比这个还小，但是仍然分得和这个值一样的糖果，因此还要从右往左再扫描一遍来补偿小的值。这个思路的代码更加精简，时间复杂度是O(n)，空间复杂度O(n)。
代码：
class Solution { public: int candy(vector<int>& ratings) { if (ratings.size() == 0) { return 0; } int len = ratings.size(), ret = 0; vector<int> nums(len, 1); for (int i = 1; i < len; ++i) { if (ratings[i] > ratings[i - 1]) { nums[i] = nums[i - 1] + 1; } } for (int i = len - 1; i > 0; --i) { if (ratings[i - 1] > ratings[i] && nums[i - 1] <= nums[i]) { nums[i - 1] = nums[i] + 1; } ret += nums[i]; } return ret + nums[0]; } };