135.分发糖果

目标

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;
    }

}

性能

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注