Candy

最优解法：
/*
方案 ：O(n)时间，O(1)空间。
不需要记录每个孩子得到的糖果数目，只需要记录前一个孩子得到的糖果candy和
当前孩子之前rating取极大值的孩子位置maxIndex，以及该位置上孩子的糖果数maxValue。
通过这个，就可以判断需不要补糖果，以及补几颗。
*/
    int candy(vector<int> &ratings) {
        int N = ratings.size();
        if (N == 0) return 0;
        int candy = 1, res = 1;
        int maxValue = 1, maxIndex = 0;
        for (int i = 1; i < N; ++i)
        {
            if (ratings[i] >= ratings[i-1])
            {
                candy = ratings[i] == ratings[i-1] ? 1 : candy + 1;
                maxValue = candy;
                maxIndex = i;
            }
            else
            {
                if (candy == 1) {
                    if (maxValue <= i - maxIndex) {
                        res += i - maxIndex;
                        maxValue++;
                    } else {
                        res += i - maxIndex - 1;
                    }
                }
                candy = 1;
            }
            res += candy;
        }
        return res;
    }

//another one


int candy_2(vector<int> &ratings) {
    int N = ratings.size();
    if (N == 0) return 0;
    int candy[N];
    for (int i = 0; i < N; ++i)
        candy[i] = 1;
    for (int i = 1; i < N; ++i)
        if (ratings[i] > ratings[i-1])
            candy[i] = candy[i-1] + 1;
    for (int i = N-2; i >= 0; --i)
        if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1])
            candy[i] = candy[i+1] + 1;
    int res = 0;
    for (int i = 0; i < N; ++i)
        res += candy[i];
    return res;
}

另外一种次优的解法：
http://codeganker.blogspot.com/2014/03/candy-leetcode.html