什么网站可以做长图攻略,网站策划书案例展示,国外做海报的网站,米拓建站教程目录 一、题目二、解法完整代码 一、题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求#xff0c;给这些孩子分发糖果#xff1a;
每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子… 目录 一、题目二、解法完整代码 一、题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
示例 1
输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。 示例 2
输入ratings [1,2,2] 输出4 解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果这满足题面中的两个条件。
提示
n ratings.length 1 n 2 * 104 0 ratings[i] 2 * 104 二、解法
根据题目要求两个数相邻若不想等那么比较大的那个数分得的糖果更多。 假想一个最终的糖果数组我们如何检查呢可以先统一检查左侧再统一检查右侧。 统一检查左侧左边比自己评分低的那么糖果数一定要小于自己 统一检查右侧右边… 利用left和right数组来存储每一侧至少应该放多少个糖果刚开始每个小孩先分一个然后少的再补 完整代码
class Solution:def candy(self, ratings: List[int]) - int:n len(ratings)left [1] * nright [1] * nfor i in range(1, n):if ratings[i] ratings[i - 1]: left[i] left[i - 1] 1if ratings[n - i - 1] ratings[n - i]:right[n - i - 1] right[n - i] 1res 0for i in range(n):res max(left[i], right[i])return res
