題目
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;
vector<int> num(ratings.size(), 1);
for (int i = 0; i < (int)ratings.size() - 1; ++i) {
if (ratings[i + 1] > ratings[i]) num[i + 1] = num[i] + 1;
}
for (int i = (int)ratings.size() - 1; i > 0; --i) {
if (ratings[i - 1] > ratings[i]) num[i - 1] = max(num[i] + 1, num[i - 1]);
}
for (int i = 0; i < num.size(); ++i) {
res += num[i];
}
return res;
}
};
分析
這道題看起來很難，其實解法并沒有那么復雜烦却。
首先初始化每個人一個糖果宠叼，然后這個算法需要遍歷兩遍，第一遍從左向右遍歷，如果右邊的小盆友的等級高冒冬，等加一個糖果伸蚯，這樣保證了一個方向上高等級的糖果多。
然后再從右向左遍歷一遍简烤，如果相鄰兩個左邊的等級高剂邮，而左邊的糖果又少的話，則左邊糖果數(shù)為右邊糖果數(shù)加一横侦。
最后再把所有小盆友的糖果數(shù)都加起來返回即可挥萌。
