135. 分发糖果

🔴   🔖  贪心 数组  🔗 力扣 LeetCode

题目

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]

Output: 5

Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]

Output: 4

Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.

The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

题目大意

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

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

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

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

示例 1：

输入：ratings = [1,0,2]

输出：5

解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]

输出：4

解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

解题思路

在这个问题中，每个孩子拿到的最小糖果数取决于他左侧和右侧的孩子。因此可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理：

1. 初始化数组：

   • 使用一个数组 candy 来保存每个孩子的糖果数；
   • 初始化 candy 的每个位置为 1 ，来满足每个孩子至少分配到 1 个糖果；

2. 从左向右遍历：

   • 从左到右遍历数组，当 ratings[i−1]<ratings[i] 时，i 号孩子的糖果数量将比 i−1 号孩子的糖果数量多 1 个；

3. 从右向左遍历：

   • 从右到左遍历数组，当 ratings[i]>ratings[i+1] 时，i 号孩子的糖果数量将比 i+1 号孩子的糖果数量多 1 个；

4. 将所有孩子的糖果数相加得到最终结果

复杂度分析

• 时间复杂度: O(n)，其中 n 是数组的长度。
• 空间复杂度: O(n)。

代码

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
	const n = ratings.length;
	let candy = new Array(n).fill(1);

	for (let i = 1; i < n; i++) {
		if (ratings[i] > ratings[i - 1] && candy[i] <= candy[i - 1]) {
			candy[i] = candy[i - 1] + 1;
		}
	}

	for (let i = n - 2; i >= 0; i--) {
		if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
			candy[i] = candy[i + 1] + 1;
		}
	}

	return candy.reduce((acc, cur) => acc + cur, 0);
};

相关题目

题号	标题	题解	标签	难度
2371	最小化网格中的最大值 🔒		并查集 图 拓扑排序 3+
3122	使矩阵满足条件的最少操作次数		数组 动态规划 矩阵
3142	判断矩阵是否满足条件		数组 矩阵