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?

1 class Solution { 2 public: 3     int candy(vector
     
       &ratings) { 4         vector
      
        candy_number(ratings.size(), 1); 5         //不用迭代器，改用下标索引实现，这样代码看起来更加简洁 6         for(int i=1; i
       
         ratings[i-1])      //eg：输入[4 2 3 4 1],最少的分法是[2 1 2 3 1],分发9个糖果10                 candy_number[i] = (candy_number[i] > candy_number[i-1]+1) ? candy_number[i] : candy_number[i-1]+1;11         }12         13 14         for(int i=ratings.size()-2; i>=0; --i)   15         {16             //保障当左边的rating比右边的高时，则左边分得的糖果比右边多17             if( ratings[i] > ratings[i+1])18                 candy_number[i] = (candy_number[i] > candy_number[i+1]+1) ? candy_number[i] : candy_number[i+1]+1;19         }20 21         int total=0;22         for(int i=0; i!=ratings.size(); ++i)23             total = total + candy_number[i];24 25         return total;26     }27 };