首页 > 代码库 > Leetcode:Candy 每个数都比相邻数大
Leetcode: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?
class Solution {public: int candy(vector<int> &ratings) { std::vector<int> num(ratings.size(), 1); int inc = 2; for (int i = 1; i < ratings.size(); ++i) { if (ratings.at(i) > ratings.at(i - 1)) { num.at(i) = std::max(inc++, num.at(i)); } else { inc = 2; } } inc = 2; for (int i = ratings.size() - 2; i >= 0; --i) { if (ratings.at(i) > ratings.at(i + 1)) { num.at(i) = std::max(inc++, num.at(i)); } else { inc = 2; } } int res = std::accumulate(num.begin(), num.end(), 0); return res; }};
step1. 首先将辅助数组每个元素初始化为1,因为每个元素都至少为1
step2. 从左向右扫描,如果某个数比其左相邻数大,则num数组对应位置的这个数从2开始递增赋值 (注意相等是不需要增加的),否则递增量初始为2
遍历完之后,可以满足:如果 原数组中某个数大于其左相邻数,那么对应辅助数组中也一定是大于其左相邻数
如果 ratings[i] >= ratings[i+1] 此时ratings[i+1]一定为1
step3. 从右向左遍历,类似step2
其实step2中 num.at(i)一定是等于inc++的,因为num.at(i)未改变之前都是初始为1的
为什么step3中一定要加上 inc比num.at(i)的比较呢? 因为此时 必须满足step2之后数组的大小条件
原数组为:1 --> 2 --> 5 --> 4 --> 3 --> 2 --> 1step2之后 num数组为:1 --> 2 --> 3 --> 1 --> 1 --> 1 --> 1step3从右向左遍历到idx=2时 : 1 --> 2 --> (3 or 5)--> 4 --> 3 --> 2 --> 1
idx=2位置处,必须满足它比左相邻数大,比右相邻数大,所以才有了max操作
Leetcode:Candy 每个数都比相邻数大
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。