清河网站建设网络公司,宁波seo推广如何收费,wordpress登录后才能进入某分类,宝安区建设网站题目描述#xff1a;n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求#xff0c;给这些孩子分发糖果#xff1a; 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果#xff0c;计… 题目描述n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求给这些孩子分发糖果 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 题目详细链接 解题思路 这道题既要考虑左孩子和自己的大小还要考虑右孩子和自己的大小两边都要满足一次遍历不能两者兼顾因此需要遍历两次一次考虑 右孩子 左孩子的情况一次考虑 左孩子 右孩子的情况。 具体步骤如下 构建一个糖果数组candy []长度和孩子数组一样初始值都是1先从左到右遍历 考虑 右小孩 左小孩 的时候右小孩糖果1的情况再从右到左遍历 考虑 左小孩 右小孩 的时候左小孩糖果1的情况为什么需要从右向左遍历自己推理一下就可以理解了注意这个是在上一步的基础之上更新candy []因此要选择两次的最大值作为最终的candy[i]结果对candy []求和返回结果即可。 代码实现 class Solution {public int candy(int[] ratings) {int len ratings.length;int[] candy new int[len];// 每个孩子需要的糖果数组// 初始化糖果为 1for (int i 0; i len; i) {candy[i] 1;}// 先从左到右遍历 考虑 右小孩 左小孩 的时候右小孩糖果1的情况for (int i 1; i len; i) {if (ratings[i] ratings[i-1]){candy[i] candy[i-1]1;}}// 再从右到左遍历 考虑 左小孩 右小孩 的时候左小孩糖果1的情况for (int ilen-1;i0;i--){if (ratings[i-1] ratings[i]){candy[i-1] Math.max(candy[i] 1, candy[i-1]);// 因为第一次从左向右遍历的时候已经有值了所以这次取最大值}}int res 0;for (int i 0; i len; i) {res candy[i];// 这种方法的耗时更短}return res;
// return Arrays.stream(candy).sum();//数组求和但是效率低}
}
