【题目】
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个孩子站成一排。每个孩子都分配了一个等级值。 你把糖果给这些孩子受到以下要求：
每个孩子都必须至少有一个糖果。 具有较高等级值的孩子们比他左右小伙伴获得更多糖果。 请问你至少拿多少糖果分配给孩子们？
【分析】
思路1：
初始化所有小孩的糖果数目为1，从前往后扫描，如果第i个小孩的权值比第i-1个高，那么i的糖果数目等于i-1的糖果数目+1；从后往前扫描，
如果第i个的小孩的权值比i+1个小孩高,但是糖果的数目却小或者相等，那么i的糖果数目等于i+1的糖果数目+1。该算法时间复杂度为O(N)
【代码】
/********************************* * 日期：2014-01-25 * 作者：SJF0115 * 题号: Candy * 来源：http://oj.leetcode.com/problems/candy/ * 结果：AC * 来源：LeetCode * 总结： **********************************/ #include#include #include using namespace std; // 时间复杂度 O(n)，空间复杂度 O(1) class Solution { public: int candy(vector &ratings) { int i; int n = ratings.size(); int result = 0; vector count(n); //每一个人至少一个糖果 for(i = 0;i < n;i++){ count[i] = 1; } // 左右各扫描一遍 //从左向右扫描 for(i = 1;i < n;i++){ //如果第i个小孩等级比第i-1个高，那么i的糖数目等于i-1的糖数目+1 if(ratings[i] > ratings[i-1]){ count[i] = count[i-1] + 1; } } //从右向左扫描 for(i = n-2;i >= 0;i--){ //如果第i个的小孩的权值比i+1个小孩高,但是糖的数目却小或者相等，那么i的糖数目等于i+1的糖数目+1。 if(ratings[i] > ratings[i+1] && count[i] <= count[i+1]){ count[i] = count[i+1] + 1; } } //统计糖果数量 for(i = 0;i < n;i++){ result += count[i]; } return result; } }; int main() { Solution solution; int result; vector ratings = {2,2}; result = solution.candy(ratings); printf("Result:%d\n",result); return 0; }
【测试】
Input: [1,2,4,4,3] Expected: 9
Input: [1,2,2] Expected: 4
Input: [2,2] Expected: 2