代码随机化算法训练营第 34 天 贪婪算法 3

Day34 贪心算法3

1005.K次取反后最大化的数组和

134. 加油站

tbd

135. 分发糖果

思路

局部最优：先给第一个孩子分配最少的一个糖果，如果下一个孩子评分更低，则相应再给原来的孩子加一个糖果
不知道怎么写代码

根据代码随想录
要点：

1. 需要考虑两边的情况，要先确定一边，再确定另一边；两边一起比较会乱
2. 先确定一边：右边的小孩比左边得分高
3. 默认糖果初始数量为1，如果右边的打，那就加一
4. 左边比右边孩子得分高，需要从右往左遍历
5. 得到的两组数，取最大的

最终代码：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candy = [1] * len(ratings)
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candy[i] = candy[i - 1] + 1
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candy[i] = max(candy[i], candy[i + 1] + 1)
        return sum(candy)

总结：
模拟一下整个过程