Candy

Question

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?

Thoughts

cn blog 两种解法

Solution

class Solution:
    # @param {int[]} ratings Children's ratings
    # @return {int} the minimum candies you must give
    def candy(self, ratings):
        # Write your code here
        if not ratings:
            return 0
        result = 0
        candies = [1 for i in range(len(ratings))]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                candies[i] = candies[i-1] + 1

        for j in range(len(ratings) - 2, -1, -1):
            if ratings[j] > ratings[j+1]:
                candies[j] = max(candies[j], candies[j+1] + 1)

        result = sum(candies)

        return result

另一种一遍扫描的解法 java

class Solution {
public:
    int candy(vector<int> &ratings) 
    {
        if(ratings.size()==0)
            return 0;

        int* candy=new int[ratings.size()];
        int count=0;

        candy[0]=1;

        for(int i=1; i<ratings.size(); i++)
        {
            if(ratings.at(i)>ratings.at(i-1))
                candy[i]=candy[i-1]+1;
            else if(ratings.at(i)==ratings.at(i-1))
                candy[i]=1;
            else
            {
                candy[i]=1;
                for(int j=i-1; j>-1; j--)
                {
                    if(ratings.at(j)>ratings.at(j+1) && candy[j]<=candy[j+1])
                        candy[j]++;
                    else
                        break;
                }
            }
        }

        for(int i=0; i<ratings.size(); i++)
            count+=candy[i];

        return count;
    }
};