[LeetCode] 135. Candy

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]，则比较两种可能性

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