Candy

LeetCode #135

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:

Note

Idea:

先create一个array，都是0，是assign的candy。 往左扫一遍，如果小于左边，就对比num_candy和increase的max，然后increase增加。 然后再从右往左过一遍。

Code:

class Solution {
public:
    int candy(vector<int>& ratings) {
        int increase=1;
        int n=ratings.size();
        vector<int> num_candy(n, 0);

        for(int i=1; i<n; ++i){
            if(ratings[i]>ratings[i-1]){
                num_candy[i]=max(increase++, num_candy[i]);
            }
            else{
                increase=1;
            }
        }

        increase=1;
        for(int i=n-2; i>=0; --i){
            if(ratings[i]>ratings[i+1]){
                num_candy[i]=max(increase++, num_candy[i]);
            }
            else{
                increase=1;
            }
        }


        int min_sum=0;
        for(auto e: num_candy){
            min_sum += e;
        }
        return min_sum+n; // add n as initial value, because every child get at least one candy.

    }
};