# 135. 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) {
int res = 0, n = ratings.size();
vector<int> nums(n, 1);
for (int i = 0; i < n - 1; ++i) {
if (ratings[i + 1] > ratings[i]) nums[i + 1] = nums[i] + 1;
}
for (int i = n - 1; i > 0; --i) {
if (ratings[i - 1] > ratings[i]) nums[i - 1] = max(nums[i - 1], nums[i] + 1);
}
for (int num : nums) res += num;
return res;
}
};
``````

1. 接下来的同学的rating等于前一个同学，那么给接下来的同学一个糖果就行。

2. 接下来的同学的rating大于前一个同学，那么给接下来的同学的糖果数要比前一个同学糖果数加1。

3.接下来的同学的rating小于前一个同学，那么我们此时不知道应该给这个同学多少个糖果，需要看后面的情况。

1 3 2 1

``````class Solution {
public:
int candy(vector<int>& ratings) {
if (ratings.empty()) return 0;
int res = 1, pre = 1, cnt = 0;
for (int i = 1; i < ratings.size(); ++i) {
if (ratings[i] >= ratings[i - 1]) {
if (cnt > 0) {
res += cnt * (cnt + 1) / 2;
if (cnt >= pre) res += cnt - pre + 1;
cnt = 0;
pre = 1;
}
pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
res += pre;
} else {
++cnt;
}
}
if (cnt > 0) {
res += cnt * (cnt + 1) / 2;
if (cnt >= pre) res += cnt - pre + 1;
}
return res;
}
};
``````

https://discuss.leetcode.com/topic/5243/a-simple-solution

https://discuss.leetcode.com/topic/8208/one-pass-constant-space-java-solution

https://discuss.leetcode.com/topic/17722/two-c-solutions-given-with-explanation-both-with-o-n-time-one-with-o-1-space-the-other-with-o-n-space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation