JAVA练习367- 分发糖果

题目概览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 * 10^40 ratings[i] 2 * 10^4来源135. 分发糖果 - 力扣LeetCode解题分析方法两次遍历本题的核心要求是每个孩子至少 1 颗糖且相邻孩子中评分更高的必须获得更多糖果。为了用最少的糖果满足这两个条件我们可以采用「两次遍历」的策略分别处理从左到右和从右到左的递增关系。思路解析如果只考虑「左邻居」规则很简单若当前孩子评分比左边高则他的糖果数应比左边多 1。若当前孩子评分不高于左边则他最少可以只拿 1 颗糖因为右边还没考虑。同理如果只考虑「右邻居」若当前孩子评分比右边高则他的糖果数应比右边多 1。否则他可以只拿 1 颗糖。但题目要求同时满足左右两边的约束因此每个孩子最终的糖果数应取上述两个方向计算结果的最大值这样才能同时保证比左边高时足够多、比右边高时也足够多。算法步骤第一次遍历从左到右初始化数组left令left[0] 1。遍历i 1 → n-1若ratings[i] ratings[i-1]则left[i] left[i-1] 1保证比左边多。否则left[i] 1先给最少右边遍历时会再调整。第二次遍历从右到左初始化变量right 1最后一个孩子的右向糖果数总糖果数sum left[n-1]。遍历i n-2 → 0若ratings[i] ratings[i1]则right right 1保证比右边多。否则right 1重置为最少。此时当前孩子应得的糖果数为max(left[i], right)将其累加到sum。返回sum。代码实现Javaclass Solution { public int candy(int[] ratings) { int n ratings.length; int[] left new int[n]; // 从左到右遍历 left[0] 1; for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { left[i] left[i - 1] 1; } else { left[i] 1; } } // 从右到左遍历并累加 int right 1; int sum left[n - 1]; // 最后一个孩子的糖果数 for (int i n - 2; i 0; i--) { if (ratings[i] ratings[i 1]) { right; } else { right 1; } sum Math.max(left[i], right); } return sum; } }复杂度分析时间复杂度O(n)仅需两次线性遍历。空间复杂度O(n)用于存储左向糖果数组left。若优化为 O(1) 空间可将第二次遍历直接与第一次结合但代码会稍复杂。示例推演以ratings [1,0,2]为例左向遍历得left [1,1,2]。右向遍历时i2评分 2right1sumleft[2]2。i1评分 0因为 0 2否right1max(left[1]1, right1)1sum213。i0评分 1因为 1 0是right2max(left[0]1, right2)2sum325。最终结果 5与题目输出一致。该方法保证了每个孩子既满足左邻约束通过left数组又满足右邻约束通过动态的right变量且取最大值后即为满足双边条件的最小糖果数。