## Wednesday, November 13, 2013

### [LeetCode] Candy, Solution

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?
[Thoughts]

Candy[i] =            Candy[i-1]+1  if ratings[i] > ratings[i-1] 递增序列，后面小孩需要的糖果是前一个小孩的糖果数+1
1                   if ratings[i] == ratings[i-1] 直线，按照题意，如果两个小孩rating一样多，后面的小孩可以只拿一个糖
Candy[i-1] –1 if ratings[i] < ratings[i-1] 递减序列。这个递推式显然是有缺陷，因为如果递减序列比较长的话，Candy[i]就可能出现负值了，负值显然是没有意义的。比如下图为例：

[Code]
``````1:         int candy(vector<int> &ratings) {
2:            vector<int> candy(ratings.size());
3:            candy[0] = 1;
4:            int i =1;
5:            for (; i < ratings.size(); ++i)
6:            {
7:                 if (ratings[i] > ratings[i-1]) //递增
8:                 {
9:                      candy[i] = candy[i - 1] + 1;
10:                 }
11:                 if (ratings[i] == ratings[i-1]) //平行
12:                 {
13:                      candy[i] = 1;
14:                 }
15:                 if (ratings[i] < ratings[i - 1]) //递减
16:                 {
17:                      candy[i] = candy[i - 1] - 1;
18:                 }
19:                 if (i<ratings.size()-1 && ratings[i] < ratings[i-1] && ratings[i] <=ratings[i+1])
21:            }
22:            if (ratings[i-1] < ratings[i-2])
23:                 ReAdjustCandy(ratings, candy, ratings.size() - 1);
24:            int total = 0;
25:            std::for_each(candy.begin(), candy.end(), [&](int n){
26:                 total += n;
27:            });
29:       }
30:       void ReAdjustCandy(vector<int>& ratings, vector<int>& candy, int startIndex)
31:       {
32:            int k = startIndex;
33:            int diff = 1 - candy[k];
34:            while (k > 0 && ratings[k - 1] > ratings[k])
35:            {
36:                 candy[k] = candy[k] + diff;
37:                 k--;
38:            }
39:            if (diff > 0) candy[k] += diff;
40:       }
``````