Python面试宝典第23题:分发糖果

CSDN 2024-08-23 12:35:04 阅读 71

题目

n 个孩子站成一排,给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果。

(1)每个孩子至少分配到 1 个糖果。

(2)相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果,计算并返回需要准备的最少糖果数目 。

示例 1:

<code>输入:ratings = [1, 0, 2]

输出:5

解释:你可以分别给第一个、第二个、第三个孩子分发2、1、2颗糖果。

示例 2:

输入:ratings = [1, 2, 2]

输出:4

解释:你可以分别给第一个、第二个、第三个孩子分发1、2、1颗糖果。

第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。

贪心算法

本题最直观的解法是:使用两次遍历的贪心算法。第一次遍历:从左到右,保证每个孩子至少有一颗糖果,并且如果当前孩子评分比左边孩子高,则当前孩子至少比左边孩子多一颗糖果。第二次遍历:从右到左,再次检查每个孩子,确保如果当前孩子评分比右边孩子高,也能得到比右边孩子多的糖果。使用贪心算法求解本题的主要步骤如下。<



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。