Hard
Related Topics: Array / Greedy
LeetCode Source

解題想法

首先先確認 len(ratings)，如果小於等於 1，則直接回傳 len(ratings)

再來先初始化 candies = [1] * len(ratings)，以符合條件一

Each child must have at least one candy.

之後演算法計算條件二

Children with a higher rating get more candies than their neighbors.

先從左項目開始判斷，如果 ratings[i] > ratings[i-1]，則 candies[i-1]+1

再來判斷右項目，如果 ratings[i] > ratings[i+1]，則比較兩種可能性

• candies[i]
• candies[i + 1] + 1

Python

class Solution:
    def candy(self, ratings: List[int]) -> int:
        if len(ratings) <= 1:
            return len(ratings)
        
        candies = [1] * len(ratings)

        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        
        return sum(candies)

C++

class Solution {
public:
    int candy(vector<int>& ratings) {
        if (ratings.size() <= 1)
            return ratings.size();

        vector<int> res(ratings.size(), 1);

        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i-1])
                res[i] = res[i-1] + 1;
        }

        for (int i = ratings.size()-2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1])
                res[i] = max(res[i], res[i+1]+1);
        }

        return accumulate(res.begin(), res.end(), 0);
    }
};

accumulate(res.begin(), res.end(), 0); 可以把 res 的值加總，初始值是 0

這系列文被記錄在 Top Interview 150 Series