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；反向遍历，后者比前者小，前者加1。正向遍历一次，还是比较好想到的，那为什么要遍历两次，若整个数列是递减数列，则若只正向遍历一遍，所有得到的糖果都是1，这显然不符合题意，如4,3,2,1 ，其实只要开始时降序的就不行。那么方向遍历过程中，是不是只要前者比后者大就加1了？不是，我们举个反例“4,1,2,1”，正向遍历是，这四个小孩的得到的糖果数是：1,1,2,1，那么反向遍历时，若只要前者比后者大就加1会得到： 2,1,3,1，这显然不符合最少糖果的要求，最少应为2,1,2,1，这是因为正向遍历中，数组A[2]对应的元素值比两边都大，已经满足了其所得糖果比两边大的条件。总结一下：正向遍历，无法满足数组首元素为降序的情况；反向遍历，若只考虑前者比后者大，不满足若某元素已经取得局部最大的情况。所以此时应该加一定的限制条件，如代码所示：

1 class Solution { 2 public: 3     int candy(vector
     
       &ratings)  4     { 5         int len=ratings.size();    6         int res=0; 7         vector
      
        cans(len,1); 8         if(len<1) return 0; 9 10         for(int i=0;i
       
        0;i--)16         {17             if(ratings[i]
        
         <=cans[i])  //限定18                 cans[i-1]=cans[i]+1;19         }20 21         for(int i=0;i
        
       
      
     

 还有一种空间复杂度为O(1)的解法，见的博客，不过个人感觉思想类似，有兴趣可以看看。