目标
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 * 10^4
- 0 <= ratings[i] <= 2 * 10^4
思路
n
个孩子站成一排,ratings
表示每个孩子的评分。现在需要给孩子分发糖果,要求每个孩子至少分配一个糖果,并且相邻的两个孩子,评分高的孩子分得的糖果大于评分低的孩子分得的糖果,返回需要准备的最少糖果数目。
官网题解提供了一种常数空间复杂度的写法,记录评分严格递增与严格递减序列长度:
- 当处于严格递增序列时,分配的糖果比前面的多一个即可
- 如果评分相同,则分配一个糖果并重置序列长度
- 当处于严格递减序列时,分配递减序列长度个糖果,相当于递增序列的逆过程
- 需要特殊处理递增序列与递减序列长度相同的情况
看下面的例子:
评分 4 5 4 3 2 1,
a b c d e f
1 2 1
当处理到 c 时,处于下降序列,我们给他分配 1 个糖果
1 3 2 1
当处理到 d 时,仍处于下降序列,需要给 c 多分配一个糖果,即 2 个,发现这时与 b 分配的相同,不满足要求,需要给 b 也多分配一个,共 3 个
1 4 3 2 1
当处理到 e 时,仍处于下降序列,需要给 b c d 多分配一个,共 4 个
1 5 4 3 2 1
当处理到 f 时,仍处于下降序列,需要给 b c d e 多分配一个糖果,共 5 个
相当于往递减序列的头部插入递减序列长度个糖果,视为反向的递增,当递增序列与递减序列长度相同时需要特殊处理。
代码
/**
* @date 2024-12-11 9:18
*/
public class Candy135 {
public int candy_v3(int[] ratings) {
int n = ratings.length;
int increase = 1;
int decrease = 0;
int res = 1;
int prev = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] >= ratings[i - 1]) {
prev = ratings[i] == ratings[i - 1] ? 1 : prev + 1;
res += prev;
increase = prev;
decrease = 0;
} else {
decrease++;
if (decrease == increase) {
decrease++;
}
res += decrease;
prev = 1;
}
}
return res;
}
}