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

21-发糖果

article 2025/3/1 8:39:15

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

方法一：贪心算法

function candy(ratings: number[]): number {
    const n = ratings.length;
    const candies = new Array(n).fill(1);

    // 从左到右遍历，保证右边评分高的孩子糖果多
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // 从右到左遍历，保证左边评分高的孩子糖果多
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
            candies[i] = candies[i + 1] + 1;
        }
    }

    // 计算糖果总数
    let total = 0;
    for (const candy of candies) {
        total += candy;
    }

    return total;
}

// 示例调用
const ratings = [1, 0, 2];
const result = candy(ratings);
console.log("需要准备的最少糖果数目:", result);

代码解释

初始化糖果数组：创建一个长度为 n 的数组 candies，并将每个元素初始化为 1，表示每个孩子至少分配到 1 个糖果。
从左到右遍历：通过 for 循环从索引 1 到 n - 1 遍历数组。如果当前孩子的评分 ratings[i] 大于左边孩子的评分 ratings[i - 1]，则将当前孩子的糖果数 candies[i] 设置为左边孩子糖果数 candies[i - 1] 加 1，以满足相邻孩子评分更高的孩子获得更多糖果的条件。
从右到左遍历：再通过 for 循环从索引 n - 2 到 0 反向遍历数组。如果当前孩子的评分 ratings[i] 大于右边孩子的评分 ratings[i + 1]，并且当前孩子的糖果数 candies[i] 小于等于右边孩子的糖果数 candies[i + 1]，则将当前孩子的糖果数 candies[i] 设置为右边孩子糖果数 candies[i + 1] 加 1，进一步保证满足条件。
计算糖果总数：遍历 candies 数组，将每个孩子的糖果数累加到变量 total 中，最后返回 total，即需要准备的最少糖果数目。

复杂度分析

时间复杂度：(O(n))，其中 n 是孩子的数量。代码中进行了两次遍历数组的操作，每次遍历的时间复杂度都是 (O(n))，最后计算糖果总数的遍历时间复杂度也为 (O(n))，所以总的时间复杂度为 (O(n))。
空间复杂度：(O(n))，用于存储每个孩子分配的糖果数的数组 candies 的长度为 n，因此空间复杂度为 (O(n))。

这种贪心算法的思路通过两次遍历，分别从不同方向保证了糖果分配满足条件，从而高效地计算出了最少糖果数目。

方法二：山峰山谷想象法

思路分析

可以将孩子的评分序列看作是一系列的山峰和山谷。对于上升序列（评分递增），糖果数依次递增；对于下降序列（评分递减），糖果数也依次递减；而在山谷处（评分局部最小），糖果数为 1。我们可以通过一次遍历找出所有的上升和下降序列，然后计算每个序列所需的糖果数。

代码实现

function candy(ratings: number[]): number {
    const n = ratings.length;
    if (n <= 1) {
        return n;
    }
    let totalCandies = 0;
    let up = 0; // 上升序列的长度
    let down = 0; // 下降序列的长度
    let oldSlope = 0;

    for (let i = 1; i < n; i++) {
        // 当前的斜率，1 表示上升， -1 表示下降， 0 表示相等
        let newSlope = ratings[i] > ratings[i - 1]? 1 : (ratings[i] < ratings[i - 1]? -1 : 0);

        if ((oldSlope > 0 && newSlope === 0) || (oldSlope < 0 && newSlope >= 0)) {
            // 当上升序列结束或者下降序列结束时
            totalCandies += count(up) + count(down) + Math.max(up, down);
            up = 0;
            down = 0;
        }

        if (newSlope > 0) {
            up++;
        } else if (newSlope < 0) {
            down++;
        } else {
            totalCandies++;
        }

        oldSlope = newSlope;
    }

    // 处理最后一个上升或下降序列
    totalCandies += count(up) + count(down) + Math.max(up, down) + 1;

    return totalCandies;
}

// 计算长度为 length 的序列所需的糖果数
function count(length: number): number {
    return (length * (length + 1)) / 2;
}

代码解释

初始化变量：
- n 为孩子的数量。
- totalCandies 用于记录总共需要的糖果数，初始化为 0。
- up 记录当前上升序列的长度，down 记录当前下降序列的长度，初始都为 0。
- oldSlope 记录上一个位置的斜率，初始为 0。
遍历评分序列：
- 计算当前位置的斜率 newSlope，如果当前评分大于前一个评分，newSlope 为 1；如果小于，为 -1；如果相等，为 0。
- 当上升序列结束（oldSlope > 0 && newSlope === 0）或者下降序列结束（oldSlope < 0 && newSlope >= 0）时，计算该上升和下降序列所需的糖果数，并累加到 totalCandies 中，同时重置 up 和 down 为 0。
- 根据 newSlope 的值更新 up、down 或 totalCandies。如果 newSlope 为 1，up 加 1；如果为 -1，down 加 1；如果为 0，totalCandies 加 1。
- 更新 oldSlope 为 newSlope。
处理最后一个序列：
- 遍历结束后，处理最后一个上升或下降序列，将其所需的糖果数累加到 totalCandies 中。
计算序列所需糖果数：
- count 函数用于计算长度为 length 的序列所需的糖果数，根据等差数列求和公式 (length * (length + 1)) / 2 计算。