Skip to content

分发糖果

· 4 min

题目#

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1

输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2

输入：ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

解题思路

  1. 每个孩子至少要分得 1 个糖果，因此我们可以先创建一个数组 candies，其中每个元素都初始化为 1。
  2. 从第 2 个孩子开始（即索引 1），如果当前孩子的评分高于左边的孩子，那么他应该比左边的孩子多拿一个糖果。
  3. 仅靠左到右遍历可能无法满足右侧条件。因此，从右向左再次遍历数组，对于每个孩子，如果他的评分比右边孩子高，则他至少需要比右边孩子多一个糖果。
  4. 最终，每个孩子分到的糖果数已满足题目要求，答案即为所有孩子糖果数的总和。

没错，这也是贪心算法的体现：

在左到右的过程中，对于每个孩子，只需比较其与左侧孩子的评分关系；在右到左的过程中，只需比较其与右侧孩子的评分关系。每一步只考虑局部相邻关系，相当于是在求局部最优解，这种策略就是典型的贪心选择。

代码实现

/**
 * ratings - 每个孩子评分的数组，例如 [1,0,2]
 */
function candy(ratings) {
  const n = ratings.length
  // 一开始每个孩子都能分配到 1 个糖果
  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--) {
    // 当前孩子的评分高于右边的孩子
    // 当前孩子的糖果数首先在右边孩子的基础上 +1，同时还要与之前的值做比较
    // 取更大的值作为当前孩子得到的糖果数
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1)
    }
  }


  // 代码来到这里，现在 candies 已经存储了每个孩子至少要得到的糖果数量
  // 计算出总的糖果数
  return candies.reduce((a, b) => a + b, 0)
}

-EOF-