首页 > 代码库 > LeetCode: Candy [135]
LeetCode: Candy [135]
【题目】
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. 每个孩子至少有一块饼干
2. 分值高的孩子比他相邻孩子拿的饼干要多
问,最少给多少块饼干就可以了?
【思路】
不多给,也不少给,分值高的比相邻的多拿一块即可首先给每个孩子发一块饼干
然后,每个孩子跟他左边的孩子比,从左到右检查每个孩子,如果这个孩子的分值比他左边孩子的要高,我们再给他些饼干,让他比他左边的孩子多一块饼干。
然后,每个孩子跟他右边的孩子比,从右到左检查每个孩子,如果这个孩子的分值比他右边孩子的要高,而他的饼干数没右边孩子的多,我们要给他些饼干,让他比他右边的孩子多一块饼干。
【代码】
class Solution { public: int candy(vector<int> &ratings) { int sum=0; int size=ratings.size(); vector<int> candy(size, 1); //从左到右检查每个孩子的左邻居 for(int i=1; i<size; i++){ if(ratings[i]>ratings[i-1]) candy[i]=candy[i-1]+1; } //从右到左检查每个孩子的右邻居 for(int i=size-2; i>=0; i--){ if(ratings[i]>ratings[i+1] && candy[i]<=candy[i+1]) candy[i]=candy[i+1]+1; } //计算饼干数 for(int i=0; i<size; i++) sum+=candy[i]; return sum; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。