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?
N个孩子有不同的等级编号，站成一排等着分糖果。规定每个孩子至少有一个糖果，等级高的孩子比相邻等级低的孩子分到的糖果要多。举例说明：输入【2，2】，则每人一个糖果，共需2个；输入【1，2，3】则需要6个糖果；【2，3，2】，则需要4个糖果。使用贪心算法，先正向遍历，等级高的孩子比左相邻的孩子糖果数加1；同理，再反向遍历，则可以形成金子塔型的糖果分布。 class Solution { public: int candy(vector<int>& ratings) { if(ratings[0]==0) return 1; int n = ratings.size(); vector<int> temp(n,1); //temp记录每人手里糖果数量，初始为1 for(int i = 1;i<ratings.size();i++) { //正向遍历 if (ratings[i]>ratings[i-1]&&temp[i]<=temp[i-1]){ temp[i] = temp[i-1]+1; } } for(int i = n-1;i>=0;i--) { //反向遍历 if (ratings[i-1]>ratings[i]&&temp[i-1]<=temp[i]){ temp[i-1] = temp[i]+1; } } int sum = 0; for(int i = 0;i<n;i++) { sum += temp[i]; } return sum; } };