当前位置：首页 > news >正文

OJ练习第153题——分发糖果

news 2025/9/12 4:17:29

分发糖果

力扣链接：135. 分发糖果

题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例

在这里插入图片描述

Java代码1（两次遍历）

官解这种方法要好理解一些。

class Solution {public int candy(int[] ratings) {int n = ratings.length;int[] left = new int[n];for (int i = 0; i < n; i++) {if (i > 0 && ratings[i] > ratings[i - 1]) {left[i] = left[i - 1] + 1;} else {left[i] = 1;}}int right = 0, ret = 0;for (int i = n - 1; i >= 0; i--) {if (i < n - 1 && ratings[i] > ratings[i + 1]) {right++;} else {right = 1;}ret += Math.max(left[i], right);}return ret;}
}

Java代码2（常数空间遍历）

在这里插入图片描述

class Solution {public int candy(int[] ratings) {int n = ratings.length;int ret = 1;int inc = 1, dec = 0, pre = 1;for (int i = 1; i < n; i++) {if (ratings[i] >= ratings[i - 1]) {dec = 0;pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;ret += pre;inc = pre;} else {dec++;if (dec == inc) {dec++;}ret += dec;pre = 1;}}return ret;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/candy/solutions/533150/fen-fa-tang-guo-by-leetcode-solution-f01p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

失败代码

运行24/48，回头再来研究这种方法能不能行。和官解方法二同理。另外代码略显冗余。

class Solution {public int candy(int[] ratings) {int n = ratings.length;if(n == 1) return 1;int sum = n;int[] sub = new int[n];sub[0] = 0;int[] score = new int[n];score[0] = 0;for(int i = 1; i < n; i++) {sub[i] = ratings[i] - ratings[i - 1];}for(int i = 1; i < n; i++) {if((sub[i] > 0 && sub[i - 1] == 0) || (sub[i] > 0 && sub[i - 1] < 0) || (sub[i] < 0 && sub[i - 1] == 0) || (sub[i] < 0 && sub[i - 1] > 0)) {score[i] = 1;}if((sub[i] > 0 && sub[i - 1] > 0) || (sub[i] < 0 && sub[i - 1] < 0)) {score[i] = score[i - 1] + 1;}if(sub[i] == 0) score[i] = 0;}for(int i = 0; i < n; i++) {if(score[i] != 0) sum += score[i];}return sum;}
}