分糖果
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?
题目意思：
有N个小孩站成一条直线，每一个小孩都有一个等级的属性。按下面要求给小孩分糖果：
求你最少要给出去多少个糖果。
解题思路：
N个小孩加上属性的话，有点类似于骆驼背的那种形状。我们新建一个用来表示每个小孩得多少糖果的大小为N的vector，和题目中给的等级vector对应。
然后两次遍历原有的vector，第一遍从前面向后面遍历，第二遍从后往前。
第一遍的目的是保证队伍后面的人如果比前面的人等级高的话，后面的人的糖果比前面的人多一个，否则后面的人糖果设为1个。
但是假如有类似于 3 4 5 4 3 这种等级分布的话，第一遍遍历后result变成了 1 2 3 1 1 ，而事实上应该是 1 2 3 2 1 ，第一遍遍历时没有考虑到后两个应该是递减的关系，所以第二遍遍历的目的就是处理这种本来应该是递减顺序全都成了1的情况。
代码如下：
1 class Solution { 2 public: 3 int candy(vector<int> &ratings) { 4 int len = ratings.size(); 5 vector<int> result(len,1); 6 7 int ret = 0; 8 if(len == 0){ 9 return ret; 10 } 11 //第一遍 12 for(int i = 1; i < len; i++){ 13 if(ratings[i] > ratings[i-1]){ 14 result[i] = result[i-1] +1; 15 } 16 } 17 //第二遍 18 ret = result[len - 1]; 19 for(int i = len - 2; i >= 0; i--){ 20 if(ratings[i] > ratings[i+1]){ 21 result[i] = max(result[i],result[i+1]+1); 22 } 23 ret += result[i]; 24 } 25 26 vector<int>::iterator it = result.begin(); 27 for(; it != result.end();it++){ 28 cout << *it << "--"; 29 } 30 return ret; 31 } 32 };
【LeetCode练习题】Candy,布布扣,bubuko.com
原文：http://www.cnblogs.com/4everlove/p/3639187.html