贪心--分发糖果
程序员文章站
2022-05-28 22:10:05
1、题目描述https://leetcode-cn.com/problems/candy/老师想给孩子们分发糖果,有 N个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。按照以下要求,帮助老师给这些孩子分发糖果,老师至少需要准备多少颗糖果呢?每个孩子至少分配到 1 个糖果。相邻的孩子中,评分高的孩子必须获得更多的糖果。输入: [1,0,2]输出: 5解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。输入: [1,2,2]输出: 4解释: 你可以分别给....
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.csdn.net/IOT_victor/article/details/107496649