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?

 

注意，像 6 5 5 4 这样的 可以分 2 1 2 1 就是数字相同的不需要糖果数相同

我的思路，分别用两个vector存储递增和递减所需要的糖果，最终结果取两个的最大值

如 权重    6 6 1 5 4 4 3 7 4 2 2 2 5 4 3 5

找递增     1 1 1 2 1 1 1 2 1 1 1 1 2 1 1 2   从前向后找，初始都是1，遇到递增的就加上他前面查找的数字

找递减     1 2 1 2 1 2 1 3 2 1 1 1 3 2 1 1   从后向前找，初始都是1，遇到递增的就加上他前面查找的数字

最终        1 2 1 2 1 2 1 3 2 1 1 1 3 2 1 2

int candy(vector
     
       &ratings) {        int ans = 0;        vector
      
        candysUp(ratings.size(), 1);        vector
       
         candysDown(ratings.size(), 1);        for(int i = 1; i < ratings.size(); i++) //查找递增        {            if(ratings[i] > ratings[i - 1])            {                candysUp[i] += candysUp[i - 1];            }        }        for(int i = ratings.size() - 2; i >= 0; i--) //查找递减        {            if(ratings[i + 1] < ratings[i])            {                candysDown[i] += candysDown[i + 1];            }        }        for(int i = 0; i < ratings.size(); i++)        {            ans += max(candysUp[i], candysDown[i]);        }        return ans;    }
       
      
     

 

大神只循环一遍的思路：

其实整体思想跟上面一样，但是上面需要循环很多次是因为递增和递减分别处理。因为递减时不知道最大的数应该加几。

大神的思路是递增的就像上面那样加，但是递减的，先都加1，如果后面仍是递减的，再把之前少加的给加回来（如前面有nSeqLen个数字少加了1，就把答案直接多加一个nSeqLen）。

//大神循环一遍的代码    int candy2(vector
     
       &ratings) {
        int nCandyCnt = 0;///Total candies    int nSeqLen = 0;  /// Continuous ratings descending sequence length    int nPreCanCnt = 1; /// Previous child's candy count    int nMaxCntInSeq = nPreCanCnt;    if(ratings.begin() != ratings.end())    {        nCandyCnt++;//Counting the first child's candy.        for(vector
      
       ::iterator i = ratings.begin()+1; i!= ratings.end(); i++)        {            // if r[k]>r[k+1]>r[k+2]...>r[k+n],r[k+n]<=r[k+n+1],            // r[i] needs n-(i-k)+(Pre's) candies(k
       
        
          *(i-1))                {                     nPreCanCnt++;                }                else                {                    nPreCanCnt = 1;                }                nCandyCnt += nPreCanCnt;                nSeqLen = 0;                nMaxCntInSeq = nPreCanCnt;            }           }    }    return nCandyCnt;}