首页 > 代码库 > 【LeetCode】Candy
【LeetCode】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?
左右各遍历一次，依据前一个位置的candy数计算当前位置需要的最小candy数
由于两次遍历的结果都要满足，因此对同一位置取max即可。
class Solution {public: int candy(vector<int> &ratings) { if(ratings.empty()) return 0; vector<int>::size_type size = ratings.size(); vector<int> candies(size, 1); //from left to right for(vector<int>::size_type st = 1; st < size; st ++) { if(ratings[st] > ratings[st-1]) candies[st] = candies[st-1]+1; //else if(ratings[st] < ratings[st-1]) // candies[st] = 1; //else // candies[st] = 1; } //from right to left int Sum = candies[size-1]; for(int st = size-2; st >= 0; st --) {//attention!!! if st is unsigned int, it will out of range if(ratings[st] > ratings[st+1]) candies[st] = max(candies[st], candies[st+1]+1); //else if(ratings[st] < ratings[st+1]) // candies[st] = max(candies[st], 1); //else // candies[st] = max(candies[st], 1); Sum += candies[st]; } return Sum; }};
【LeetCode】Candy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。