贪心--分发糖果

1、题目描述

https://leetcode-cn.com/problems/candy/

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

按照以下要求，帮助老师给这些孩子分发糖果，老师至少需要准备多少颗糖果呢？

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

 

2、代码详解

两边遍历

取以上2轮遍历 left 和 right 对应学生糖果数的 最大值 ，这样则 同时满足左规则和右规则 ，即得到每个同学的最少糖果数量。

O(N)，O(N)

class Solution:
    def candy(self, ratings):
        left = [1 for _ in range(len(ratings))]
        right = left[:]
        # 左规则：从左至右遍历
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        count = left[-1]
        # print('left:', left)
        # print('count:', count)
        # 右规则：从右至左遍历
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
            count += max(left[i], right[i])  # 累加，取2轮遍历最大值
        return count

r = [5, 7, 8, 3, 4, 2, 1]
s = Solution()
print(s.candy(r))

https://leetcode-cn.com/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/

本文地址：https://blog.****.net/IOT_victor/article/details/107496649