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:
What is the minimum candies you must give?
Solution:
首先设每个孩子得到一个糖果。然后从前往后扫一遍，如果当前孩子比前一个孩子rating高，但是糖却没有他多，则让该孩子比前一个孩子多拿一个糖。一遍扫完后，满足所有rating高的孩子都比自己的左邻居糖多。然后再从后往前扫一遍，如果当前孩子比后一个孩子rating高，但是糖没有他多，则让该孩子比后一个孩子多拿一个糖。这一遍扫完，满足所有rating高的孩子都比自己的右邻居糖多。最后求和即可。
class Solution { public: int candy(vector<int> &ratings) { int len = ratings.size(), *num = new int[len]; if(len <= 1) return len; for(int i = 0;i < len;i++) num[i] = 1; for(int i = 1;i < len;i++) if(ratings[i] > ratings[i - 1] && num[i] <= num[i - 1]) num[i] = num[i - 1] + 1; for(int i = len - 2;i >= 0;i--) if(ratings[i] > ratings[i + 1] && num[i] <= num[i + 1]) num[i] = num[i + 1] + 1; int ans = 0; for(int i = 0;i < len;i++) ans += num[i]; return ans; } };
[LeetCode] Candy,布布扣,bubuko.com
原文：http://www.cnblogs.com/changchengxiao/p/3618103.html