这个题目难度很小，也是一道贪心的题目。怎么贪呢？就按照题目要求来，可是遇到这个问题怎么办：后一个比前一个小，但是后一个却是一个大于它之后数的。这个会导致选择困难，你没法选出一个优解。我的解决办法是，排序，然后对排序后的序列的索引一个一个找周围的贪心解。这样就可以很好的，解决这个问题。其实还有一种更简单的办法，就是前向，找前一个比后一个大的计算好数组后，在后向找后一个比前一个大的。就可以了。我的代码如下：
class Solution { public: struct cmp{ bool operator()(const pair<int,int> &a,const pair<int,int> &b){ return a.second <= b.second; } }; int candy(vector<int>& ratings) { int len = ratings.size(); if(len==1)return 1; int *dp = new int[len]; vector<pair<int,int>> p; map<int,int>s; for(int i=0;i<len;i++) { s.insert(pair<int,int>(i,ratings[i])); } map<int,int>::iterator ptr1; for(ptr1 = s.begin();ptr1!=s.end();++ptr1) p.push_back(make_pair(ptr1->first,ptr1->second)); sort(p.begin(),p.end(),cmp()); for(int i = 0;i<len;i++) dp[i]=1; vector<pair<int,int>>::iterator ptr; int res = 0; for(ptr=p.begin();ptr!=p.end();++ptr) { int cur = ptr->first; //cout<<ratings[cur]<<endl; if(((ptr->first)-1)>=0&&((ptr->first)+1)<len) { int pre = (ptr->first)-1,next = (ptr->first)+1; // cout<<"pre: "<<ratings[pre]<<" "<<"cur: "<<ratings[cur]<<"next: "<<ratings[next]<<endl; if(ratings[cur]>ratings[pre]&&ratings[cur]<=ratings[next]) { dp[cur] = dp[pre]+1; } else if(ratings[cur]>ratings[next]&&ratings[cur]<=ratings[pre]) { dp[cur] = dp[next]+1; } else if(ratings[cur]>ratings[pre]&&ratings[cur]>ratings[next]) { dp[cur] = max(dp[next],dp[pre])+1; } } else if(((ptr->first)-1)<0) { int next = (ptr->first)+1; if(ratings[next]<ratings[cur])dp[cur]=dp[next]+1; } else if(((ptr->first)+1)>=len) { int pre = (ptr->first)-1; if(ratings[pre]<ratings[cur])dp[cur]=dp[pre]+1; } res+=dp[cur]; } /*cout<<endl; for(int i = 0;i<len;i++) cout<<dp[i]<<endl;*/ return res; } };