題目:
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?
思路:
本題的總體政策還是貪心法。我開始的思路是:将小孩子們按照rating的升序進行排序,然後依次配置設定糖果:如果他的某個鄰居或者兩個鄰居已經配置設定糖果了并且他的rating不大于他的鄰居的rating(不可能小于的),那麼配置設定和他的鄰居相同數目的糖果;如果他的rating高于他的某個鄰居,那麼配置設定他的鄰居糖果數目+1。如果他的鄰居尚未配置設定糖果,則隻給配置設定1個。這個思路是可行的,但是代碼複雜,時間複雜度為O(nlogn),空間複雜度O(n)。
采用兩邊掃描的方法可以将時間複雜度降為O(n)。具體方法如下:先從左往右掃描一遍,如果後面一個比前面大,那麼他配置設定的就多一顆糖果,否則就是1。但是這樣會産生一個情況,就是兩個相鄰的排名一樣,那麼後一個還是分一個,但是右面的小孩的rating可能比這個還小,但是仍然分得和這個值一樣的糖果,是以還要從右往左再掃描一遍來補償小的值。這個思路的代碼更加精簡,時間複雜度是O(n),空間複雜度O(n)。
代碼:
class Solution {
public:
int candy(vector<int>& ratings) {
if (ratings.size() == 0) {
return 0;
}
int len = ratings.size(), ret = 0;
vector<int> nums(len, 1);
for (int i = 1; i < len; ++i) {
if (ratings[i] > ratings[i - 1]) {
nums[i] = nums[i - 1] + 1;
}
}
for (int i = len - 1; i > 0; --i) {
if (ratings[i - 1] > ratings[i] && nums[i - 1] <= nums[i]) {
nums[i - 1] = nums[i] + 1;
}
ret += nums[i];
}
return ret + nums[0];
}
};