目标
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;
}
}
性能
