leetcode135. Candy

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个孩子站在一条线上。每个孩子都被分配一个权值。

要求：每个孩子必须至少有一个糖果。具有较高权值的孩子比邻居获得更多的糖果。

仅从题意看，

①每个孩子所得到的糖果要受邻居的影响；

②整个数组中，权值符合w[i]<w[i-1]&&w[i]<w[i+1]的孩子所得到的糖果为1，并将整个数组划分成一个个区域，每个区域呈倒V字型；

③在每个区域中，最高权值的孩子又将所在区域划分成两个部分；

④综上，从每个区域的两端往最高权值处遍历，就可以得到每个孩子应分到的糖果数量；

⑤最高权值的孩子所得糖果count[i]=max(count[i-1]+1,count[i+1]+1)；

这就是大概思路。另外，

⑥权值相互独立，仅糖果数量受到邻居影响；

⑦多个连续的孩子权值相等时，他们所得到的糖果数量应该一致；

以上并没有在题目中说明，我当然默认其成立，例如权值为[1,2,2]：

则其分配的糖果数量应为[1,2,2]，但testcase中给出的是[1,2,1]，这简直就是由testcase在决定一道题。。。

关于这个问题，在leetcode上有讨论：https://discuss.leetcode.com/topic/10175/why-two-adjacent-children-with-equal-rating-don-t-get-equal-candies

所以这道题目说明并不严谨的题浪费了我一天时间，题目当中忽略不提某些必要信息，把我引到了另一个逻辑上，然而这些信息却在testcase中隐晦地呈现出来，给出的某些testcase和我预想中的不一样，当然实现逻辑也不一样。虽然最终也可以实现，但我并不打算现在重新做了，以后有时间再做吧。

下面是我实现上述逻辑的代码，两种方法

 1 class Solution{
 2 public:
 3     int candy(vector<int> &ratings){
 4         int *candyCount=new int[ratings.size()];
 5         int count=0;
 6         candyCount[0]=1;
 7         for(int i=1;i<ratings.size();++i){
 8             if(ratings[i]<ratings[i-1]){
 9                 candyCount[i]=1;
10                 int flag=i;
11                 while((flag!=0)&&(ratings[flag-1]>=ratings[flag])){
12                     if(ratings[flag-1]>ratings[flag]){
13                          candyCount[flag-1]<=candyCount[flag]?candyCount[flag-1]=candyCount[flag]+1:candyCount[flag-1]=candyCount[flag-1];
14                     }else{
15                         candyCount[flag-1]=candyCount[flag];
16                     }
17                     flag--;
18                 }
19                 continue;
20             }
21             ratings[i]>ratings[i-1]?candyCount[i]=candyCount[i-1]+1:candyCount[i]=candyCount[i-1];
22         }
23         for(int i=0;i<ratings.size();++i){
24             count+=candyCount[i];
25         }
26         delete []candyCount;
27         return count;
28     }
29 };

 1 class Solution{
 2   public:
 3     int candy(vector<int> &ratings){
 4         int start = 0, end, count = 0; //start=right
 5         int candyCount[1000];          //储存每个人的糖果数量
 6         ratings.push_back(-1);
 7         if (ratings.size() == 2)    return 1;
 8         for (int i = 0; i < ratings.size(); ++i){
 9             if ((ratings[i] <= ratings[i - 1] && ratings[i] < ratings[i + 1]) || (i - 1 < 0 && ratings[i] < ratings[i + 1]) || (i + 1 > ratings.size() - 1 && ratings[i] < ratings[i - 1])){
10                 candyCount[i] = 1;
11                 end = i;
12                 if (end == start)   continue;
13                 vector<int>::iterator maxelem = max_element(ratings.begin() + start, ratings.begin() + end);
14                 int flag = std::distance(ratings.begin(), maxelem);
15                 for (int m = start + 1; m < flag; ++m)
16                     ratings[m] > ratings[m - 1] ? candyCount[m] = candyCount[m - 1] + 1 : candyCount[m] = candyCount[m - 1];
17                 for (int n = end - 1; n > flag; --n){
18                     ratings[n] > ratings[n + 1] ? candyCount[n] = candyCount[n + 1] + 1 : candyCount[n] = candyCount[n + 1];
19                     if ((end == ratings.size() - 1) && (n == end - 1))  candyCount[n]--;
20                 }
21                 if (ratings[flag] == ratings[flag + 1]){
22                     candyCount[flag - 1] < candyCount[flag + 1] ? candyCount[flag] = candyCount[flag + 1] : candyCount[flag] = candyCount[flag - 1] + 1;
23                     while ((ratings[flag] == ratings[flag + 1])&&(flag+1<ratings.size()))
24                         candyCount[flag + 1] = candyCount[flag++];
25                 }else{
26                     candyCount[flag - 1] > candyCount[flag + 1] ? candyCount[flag] = candyCount[flag - 1] + 1 : candyCount[flag] = candyCount[flag + 1] + 1;
27                 }
28                 start = i;
29             }
30         }
31         for (int k = 0; k < ratings.size() - 1; ++k)
32             count += candyCount[k];
33         return count;
34     }
35 };