贪心算法，从局部最优推广成全局最优。
这里介绍O(n)时间 O(n)和O(1)空间的两种实现方法。
O(n)时间 O(n)空间实现，参考了cnblog, 1957的解法
创建candy数组，初始化为1. 用pre_child_candy记录前一个孩子拿到的糖果数
1. 从左往右遍历
1) 如果ratings[i] > ratings[i-1], 那么candy[i] = ++ pre_child_candy, 亦即这个孩子比前一个孩子多拿一个糖果
2) 反之，candy[i] = pre_child_candy = 1. (注意到我们已经将candy全部初始化为1了)
2. 从右往左遍历，pre_child_candy初始化为1, 做类似的操作
1) 如果ratings[i-1] > ratings[i], 那么candy[i] = max(++ pre_child_candy, candy[i]), 注意到这里采用max函数是因为此时的candy同时应该满足1中从左往右遍历的约束。
2) 反之，candy[i] = pre_child_candy = 1.
这样我们最低限度地实现了题目的约束，每个较高分的孩子所得的糖果都比其相邻的孩子所得的糖果多，从局部最优推广到了全局最优。
代码：
class Solution {public:int candy(vector<int> &ratings){vector<int> candy(ratings.size(), 1);for (int pre_child_candy=1, i=1; i < ratings.size(); ++ i){if (ratings[i] > ratings[i-1]){candy[i] = ++ pre_child_candy;} else{pre_child_candy = 1;}}for (int pre_child_candy=1, i=static_cast<int>(ratings.size())-2; i >= 0; — i){if (ratings[i] > ratings[i+1]){candy[i] = max(++ pre_child_candy, candy[i]);} else{pre_child_candy = 1;}}return accumulate(candy.begin(), candy.end(), 0);}};
O(n)时间 O(1)空间实现，参考了cnblog, Felix的博客，但不同的是，在此对递增、递减、相等三种情况进行了分类讨论
tot: 糖果总数，初始化为1
dec_length: 递减序列的长度，初始化为0
candy_before_dec: 给出现递减序列前的那个孩子发出的糖果，初始化为1
pre_child_candy: 给前一个孩子发出的糖果，初始化为1
1. 如果仅考虑递增序列
亦即恒有 ratings[i] > ratings[i – 1]
从下标i = 1开始访问，那么只需要在每次迭代中，执行tot += ++ pre_child_candy即可。
2. 考虑含有递减子序列的ratings[] = {1, 4, 3, 2, 1}; 正确的糖果数应该为1, 4, 3, 2, 1
i = 1, ratings[1] > ratings[0],
tot += ++ pre_child_candy; //第二个孩子只分到了2个糖果，先别着急，后面会“补偿”他pre_child_candy, candy_before_dec都指向第二个孩子，此时它们也都等于2. 也就是i = 2, ratings[2] < ratings[1] (ratings[i] < ratings[i – 1])
我们认为这是递减序列的开始，++ dec_length; (dec_length等于1了).tot += dec_length; // tot += 1pre_child_candy = 1; // 更新它，防止潜在的递增序列需要这个变量i = 3, ratings[3] <ratings[2]++ dec_length; (dec_length == 2 now)tot += dec_length; // tot+=2pre_child_candy = 1; // 更新它，，防止潜在的递增序列需要这个变量// 这时候发现，dec_lenght >= pre_child_candy, // 递减序列的长度已经大于“给出现递减序列前的那个孩子发出的糖果”,我们就补偿给第二个孩子1个糖果，++ tot
i = 4, ratings[4] < ratings[3]
++ dec_length; (dec_length == 3 now)tot += dec_length; // tot+=3pre_child_candy = 1; // 更新它，防止潜在的递增序列需要这个变量// 这时候发现，dec_lenght >= pre_child_candy, // 递减序列的长度已经大于“给出现递减序列前的那个孩子发出的糖果”,我们就补偿给第二个孩子1个糖果，++ tot我们最后就发现，我们成功的给第二个孩子了4个糖果，而i=2,3,4的情况，则分别给tot增加了1,2,3, 这刚好是实际情况的逆序。
所以，我们处理好了含有递减子序列的情况
3. 考虑相邻孩子ratings相等的情况，可以考虑ratings[] = {1, 4, 4, 3, 2, 1}
从逻辑上，这个孩子暂时只需要给1个糖果，同时将递减序列长度归零，candy_before_dec和pre_child_candy置1即可。
代码：
class Solution {public:int candy(vector<int> &ratings){int tot = 1, dec_length = 0, candy_before_dec = 1, pre_child_candy = 1;for (int i = 1; i < ratings.size(); ++ i){if (ratings[i] > ratings[i-1]){tot += ++ pre_child_candy;dec_length = 0;candy_before_dec = pre_child_candy;} else if (ratings[i] == ratings[i-1]){++ tot;dec_length = 0;candy_before_dec = pre_child_candy = 1;} else // <{tot += ((++dec_length>=candy_before_dec)? 1: 0);tot += dec_length;pre_child_candy = 1;}}return tot;}};
人，都有不能称心如意的时候，都有愿望落空的窘迫，
