欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

贪心--分发糖果

程序员文章站 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