首页 > 代码库 > leetcode[135] Candy
leetcode[135] Candy
最少糖果问题。一排小孩，每个孩子有一个优先级，每个孩子至少要发给一个糖果，优先级高的比周围的孩子的糖果要多。
需要注意的是，优先级一样的没有要求说一样多糖果！
先初始化，每人一糖。
为了保证优先级大的比相邻的且优先级小的要糖果多。所以我们分两次处理，一次处理比左边的多，一次处理兼顾左边的多的情况下比右边的多。（如果优先级满足多的前提）
那么第一次从左到右，if (ratings[i] > ratings[i-1]) 那么cd[i] = cd[i-1]+1; cd指糖果数组
从右边到左边需要注意的是要保证之前的左到右不能减少，所以有一个max取值的问题，也就是需要更改后的如果比原来的值小，那就不用改了，如果改了变大才要改，因为如果改小就不符合大于左边的要求了。即 if(ratings[i] > ratings[i+1]) cd[i] = max(cd[i], cd[i-1]+1)
class Solution {public:int candy(vector<int> &ratings) { vector<int> cd(ratings.size(), 1); int sum = 0; for (int i = 1; i < ratings.size(); i++) { if (ratings[i] > ratings[i-1]) cd[i] = cd[i-1] + 1; } for (int i = ratings.size() - 2; i >= 0; i--) { if (ratings[i] > ratings[i+1]) cd[i] = max(cd[i], cd[i+1] + 1); } for (int i = 0; i < cd.size(); i++) { sum += cd[i]; } return sum; } };
leetcode[135] Candy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。