LeetCode 135. Candy [Hard] [C++] 解題筆記

 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?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

想法:

    這題乍一看的時候沒啥頭緒，但仔細想一下之後就發現其實只要用 Greedy 的方式掃兩次整個array就好，第一次從

頭開始，第一個小孩直接先給 1 顆，之後的人每個都只要往前看如果 rating 比前一個人高就給它多一顆，之後在從尾往頭 

做一次一樣的事就行了!

完整程式碼:

/* O(n) time, O(n) space */
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 0);        
        candies[0] = 1;
        for (int i = 1; i < ratings.size(); i++) {
            candies[i] = (ratings[i] > ratings[i - 1])? candies[i - 1] + 1 : 1;
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            candies[i] = (ratings[i] > ratings[i + 1])? max(candies[i], candies[i + 1] + 1) : candies[i];
        }
        /*for (int i = 0; i < candies.size(); i++) {
            cout<<candies[i]<<" ";
        }
        cout<<endl;*/
        return accumulate(candies.begin(), candies.end(), 0);
    }
};