135. Candy

problem description

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?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

algorithm thought

使用一个数组表示给所有小朋友分配的糖果，开始所有的小朋友都是1个。

一个小朋友等级比旁边的高的话，他的糖果必须必旁边的多。旁边有两个，首先我们让所有小孩向左看时，满足条件，然后让所有小孩往右看时满足条件，最后就能有结果。

code

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        vector<int> res(n,1);
        for(int i=1;i<n;++i)
            if(ratings[i-1]<ratings[i])
                res[i]=res[i-1]+1;
        int re=res[n-1];
        for(int i=n-2;i>=0;--i){
            if(ratings[i]>ratings[i+1])
                res[i]=max(res[i],res[i+1]+1);
            re+=res[i];
        }
        return re;
    }
};

algorithm analysis

算法两次遍历数组,最后时间复杂度O(n).