怎么发布网站,上海中风险地区有哪些,还有什么类型的网站,创建站点如何做网站n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求#xff0c;给这些孩子分发糖果#xff1a;
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果#xff0c;计算并返回需要准备的…n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 示例 1
输入ratings [1,0,2]
输出5
解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2
输入ratings [1,2,2]
输出4
解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。 提示
n ratings.length1 n 2 * 0 ratings[i] 2 * 思路
本题可采用贪心思路确定每个孩子的糖果数。
先从左向右比最左边的孩子的糖果数为 1如果右边的孩子的评分高于左边的孩子则给右边孩子的糖果数为左孩子的糖果数1若右边的孩子评分不高于左边的孩子则给一个糖果。这样会让比左边的孩子评分高的孩子得到更多的糖果。此时也初步形成了当前糖果分配数组 candyNums 。
再从右往左比如果左边的孩子的评分高于右边的孩子的评分则 左边的孩子所分得的糖果数为 当前糖果数用于保底如果 右边的孩子的糖果数1 当前糖果数则当前糖果数不变这时可以满足之前从左往右比确定的条件又可以满足大于右边孩子糖果数的条件右边的孩子的糖果数1保证左边的孩子的糖果大于右边的孩子 两者之间的最大值此时既满足从左往右确定的条件又满足从右往左确定的条件。
代码
class Solution {public int candy(int[] ratings) {int len ratings.length;int[] candyNums new int[len];candyNums[0]1;for(int i1;ilen;i){if(ratings[i]ratings[i-1]){//从左往右比如果右边的孩子评分高于左边的孩子则右边的孩子糖果数比左边的孩子多一个candyNums[i]candyNums[i-1]1;}else{//否则给一个糖果candyNums[i]1;}}//从右往左比如果左边的孩子评分高于右边的孩子则左边的孩子分得的糖果数为//当前糖果数与右边孩子糖果数1 两者之间的最大值为了保证比左右孩子都评分高的孩子的糖果数比左右孩子都多for(int ilen-2;i0;i--){if(ratings[i]ratings[i1]){candyNums[i] Math.max(candyNums[i],candyNums[i1]1);}}int ans 0;for(int x:candyNums){ans x;}return ans;}
}
参考代码随想录
