# [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) {
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;
}
};

+ 订阅