题目描述：

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个号每个号至少分一个糖，而且排名高的要比排名低的多，觉得就上个排序就了事，nlogn的复杂度应该还是可以接受的吧。于是就开始狂WA了，有以下两个个原因，首先是对rating的理解错误，其实rating应该是数字越小越高，还有一个更加隐蔽的东西，就是它上面的那两个requirement很容易误导我们，第二个其实说的是每个rating高的人必须是比邻居高，也就是说对于和两边相等的我们可以分配一个就行了（这个是过了才领悟到，极其痛苦啊）。

不过后来题目理解完了发现超时了，看来nlogn的算法还是不够优秀，于是就把排序扔了（后来才发现排序本就是错的）。在正确理解题目意思的情况直接扫两遍记录一下就行了。

这里给出几组测试数据，也帮助一下同挂在这个地方的人。

case1：input：[2,3,2]

　　　　output：4

case2：input：[1,2,2,2,3,2,1]

output：11

代码如下：

 class Solution {

 public:

     int candy(vector<int> &ratings) {

         if(ratings.empty()){

             return ;

         }

         if(ratings.size()==){

             return ;

         }

         int l=ratings.size();

         int* temp=new int[l];

         temp[]=;

         for(int i=;i<l;i++){

             if(ratings[i]>ratings[i-]){

                 temp[i]=temp[i-]+;

             }

             else{

                 temp[i]=;

             }

         }

         int ans=temp[l-];

         for(int i=l-;i>=;i--){

             if(ratings[i]>ratings[i+]&&temp[i+]+>temp[i]){

                 temp[i]=temp[i+]+;

             }

             ans+=temp[i];

         }

         return ans;

     }

 };