题目：
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?
理解题目是个蛋疼的东西。
题目大意：几个小孩站一排，每个小孩有个等级值，现在给小孩发糖，发的时候要遵守2个规则：
（1）每个小孩至少一颗糖
（2）两个相邻的小孩中，等级大的小孩一定比等级小的小孩糖多，求发糖的数目的最小值。（等级相同的可以有多有少）
根据题目的意思，我们可以知道为了确保左边和右边等级有相差的，分的糖果不一样。所有我们可以把数组从左边看，然后左边比右边等级大的，可以拿到多的糖果，再然后从右边看，右边比左边等级大的，可以拿到多的糖果。
具体算法如下：
算法2
：初始化所有小孩糖数目为1，
从前往后扫描，如果第i个小孩等级比第i-1个高，那么i
的糖数目等于i-1的糖数目+1；从后往前扫描，如果第i个的小孩的等级比i+1个小孩高,但是糖的数目却小或者相等，那么i的糖数目等于i+1的糖数目+1。
该算法时间复杂度为O(N)
具体代码实现如下所示：
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|
class Solution { public : int candy(vector< int > &ratings) { int len = ratings.size(); vector< int > candyNum(len, 1 ); for ( int i = 1 ; i < len; i++) { if (ratings[i – 1 ] < ratings[i]) { candyNum[i] = candyNum[i – 1 ] + 1 ; } } } |