首页 > 代码库 > Candy

Candy

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?

class Solution {public://two pass, one from the left, other from the right. the left one find the least number of candy that needed according the the left side//right one find the least number of candy that needed according to the right side.    int candy(vector<int>& ratings) {        if (ratings.empty())            return 0;        if (ratings.size() == 1)            return 1;        int n = ratings.size();        vector<int> candy(n,1);        for(int i=1; i < n; i++){            if (ratings[i] > ratings[i-1])                candy[i] = candy[i-1] + 1;        }        int total = candy[n-1];        for(int i=n-2; i>=0; i--){            if (ratings[i] > ratings[i+1])                candy[i] = max(candy[i], candy[i+1]+1);            total += candy[i];        }        return total;    }};

 

Candy