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

算法-遍历分发糖果

article 2025/1/30 3:49:18

hello 大家好！今天开写一个新章节，每一天一道算法题。让我们一起来学习算法思维吧！

在这里插入图片描述

function candy(ratings) {
    // 获取孩子的数量
    const n = ratings.length;
    // 初始化一个长度为 n 的数组 candies，用于存储每个孩子分配到的糖果数，初始每个孩子至少有 1 颗糖果
    const candies = new Array(n).fill(1);

    // 从左到右遍历孩子的评分数组
    for (let i = 1; i < n; i++) {
        // 如果当前孩子的评分比前一个孩子高
        if (ratings[i] > ratings[i - 1]) {
            // 那么当前孩子的糖果数要比前一个孩子多 1 颗
            candies[i] = candies[i - 1] + 1;
        }
    }

    // 从右到左遍历孩子的评分数组
    for (let i = n - 2; i >= 0; i--) {
        // 如果当前孩子的评分比后一个孩子高
        if (ratings[i] > ratings[i + 1]) {
            // 取当前孩子已分配的糖果数和后一个孩子糖果数加 1 中的较大值
            // 这样能保证既满足从左到右的规则，也满足从右到左的规则
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    // 计算所有孩子分配到的糖果总数
    let totalCandies = 0;
    for (let i = 0; i < n; i++) {
        totalCandies += candies[i];
    }

    return totalCandies;
}

// 示例测试
const ratings = [1, 0, 2];
console.log(candy(ratings));

代码解释

整体思路
本题要求给孩子们分糖果，需要满足每个孩子至少有 1 颗糖果，并且相邻孩子中评分高的孩子获得更多糖果。为了满足这些条件，我们可以采用两次遍历的方法：
第一次从左到右遍历，保证每个孩子如果比其左边孩子评分高，那么他的糖果数比左边孩子多。
第二次从右到左遍历，保证每个孩子如果比其右边孩子评分高，那么他的糖果数比右边孩子多。同时在这个过程中要取满足两次遍历规则的最大值。
最后将每个孩子的糖果数累加起来，得到最少需要准备的糖果总数。