您现在的位置是:主页 > news > 网站接入协议及接入商资质/网络营销服务公司
网站接入协议及接入商资质/网络营销服务公司
admin2025/5/20 17:09:03【news】
简介网站接入协议及接入商资质,网络营销服务公司,杭州建模培训,广州seo推广营销135. 分发糖果 - 力扣(LeetCode) 一、题目 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求,给这些孩子分发糖果: 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多…
135. 分发糖果 - 力扣(LeetCode)
一、题目
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
二、代码
class Solution {public static int candy(int[] ratings) {if (ratings == null || ratings.length == 0) {return 0;}// 构造预处理数组int[] left = new int[ratings.length];int[] right = new int[ratings.length];// 从左向右构造left[0] = 1;for (int i = 1; i < ratings.length; i++) {if (ratings[i - 1] < ratings[i]) {left[i] = left[i - 1] + 1;// 我们不管相邻两个数相等的情况,题目要求最少准备多少个,所以碰到相等或小于相邻人的情况下,直接赋值为1,这样就能取得最少准备的个数。 } else {left[i] = 1;}}// 从右向左构造right[ratings.length - 1] = 1;for (int i = ratings.length - 2; i >= 0; i--) {if (ratings[i + 1] < ratings[i]) {right[i] = right[i + 1] + 1;} else {right[i] = 1;}}// 取每个位置的最大值,就能保证题目的要求int sum = 0;for (int i = 0; i < ratings.length; i++) {sum += Math.max(left[i], right[i]);}return sum;}
}
三、解题思路
从左边开始,向右生成left数组,left数组代表每一个点左边的坡度。
下标0位置左边没东西,所以给他发1块糖,后续位置只要是得分比左边大,发糖数就比左边的人加1个,如果碰到得分不再大了,发糖数就重新给1,再从1开始++。
从右边开始,向左生成right数组,right数组代表每一个点右边的坡度。
下标n-1位置右边没东西1块糖,剩余的小朋友比右边大了了就++,不再大了就回到1。
left数组和right数组对应的每个位置的max就是这个位置的小朋友应该分糖数量,将每个位置要分糖得数量累加就是最终要准备的糖的总数。左坡和右坡以较大坡为准,因为这样才能保证如果分数比左右两边得大,拿得到糖比左右两边的人都多。