solved 'Candy' on LeetCode (needs sorting, thusO(n^2)) http://oj.leetcode.com/problems/candy/

candy.cpp

class Solution {
public:
    int candy(vector<int> &ratings) {
        int size = (int)ratings.size();
        if (size == 0 || size == 1) return size;
        vector<int> indices, candies;
        for (int i=0; i<size; ++i) {
            indices.push_back(i);
            candies.push_back(1);
        }
        MyComparator myComparator(ratings);
        sort(indices.begin(), indices.end(), myComparator);

        int minSum=0;
        for (int i=0; i<size; ++i) {
            int index = indices[i], neighborMaxCandy = 0;
            if (index != 0) {
                if (ratings[index] > ratings[index-1])
                    neighborMaxCandy = candies[index-1];
            }
            if (index != size-1) {
                if (ratings[index] > ratings[index+1] &&
                        neighborMaxCandy < candies[index+1])
                    neighborMaxCandy = candies[index+1];
            }
            candies[index] = neighborMaxCandy + 1;
            minSum += candies[index]; 
        }
        return minSum;
    }

private:
    struct MyComparator {
        MyComparator(vector<int> &ratings) {
            myRatings = &ratings;
        }
        bool operator() (int i,int j) { 
            return (*myRatings)[i] < (*myRatings)[j];
        }
        vector<int> *myRatings;
    }; 
};