江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第135题：分发糖果

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

题目描述

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

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

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

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

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 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

解题思路

方法一：两次遍历

这道题要求我们给每个孩子分发糖果，满足两个条件：每个孩子至少有1个糖果，评分高的孩子比相邻的评分低的孩子有更多的糖果。

关键点：

  • 从左到右遍历，确保右边评分更高的孩子比左边的孩子糖果数更多
  • 从右到左遍历，确保左边评分更高的孩子比右边的孩子糖果数更多
  • 取两次遍历结果的最大值，确保同时满足两个方向的要求

具体步骤：

  1. 初始化一个长度为n的数组candies，所有元素初始化为1（每个孩子至少有1个糖果）
  2. 从左到右遍历ratings数组：
    • 如果ratings[i] > ratings[i-1]，则candies[i] = candies[i-1] + 1
  3. 从右到左遍历ratings数组：
    • 如果ratings[i] > ratings[i+1]，则candies[i] = max(candies[i], candies[i+1] + 1)
  4. 计算candies数组的总和，即为最少需要的糖果数

时间复杂度：O(n)，其中n是孩子的数量。需要遍历两次ratings数组。 空间复杂度：O(n)，需要一个长度为n的数组存储每个孩子分得的糖果数。

方法二：常数空间的一次遍历

我们可以通过观察发现，糖果分配的结果实际上是由一个个“上升”和“下降”的序列组成的。

关键点：

  • 上升序列：从左到右评分递增，糖果数也递增
  • 下降序列：从左到右评分递减，糖果数也递减
  • 平坦序列：评分相等，糖果数重置为1

具体步骤：

  1. 初始化总糖果数为1（第一个孩子至少有1个糖果）
  2. 初始化当前糖果数为1，上升序列长度为0，下降序列长度为0
  3. 遍历ratings数组（从第二个孩子开始）：
    • 如果ratings[i] > ratings[i-1]（上升），当前糖果数加1，更新总糖果数
    • 如果ratings[i] < ratings[i-1]（下降），下降序列长度加1，更新总糖果数
    • 如果ratings[i] == ratings[i-1]（平坦），当前糖果数重置为1，更新总糖果数
  4. 返回总糖果数

时间复杂度：O(n)，其中n是孩子的数量。只需要遍历一次ratings数组。 空间复杂度：O(1)，只需要常数级别的额外空间。

图解思路

两次遍历分析表

以示例1为例：ratings = [1,0,2]

第一次遍历（从左到右）

索引 ratings[i] 比较 candies[i] 说明
0 1 - 1 第一个孩子，至少有1个糖果
1 0 0 < 1 1 评分比左边低，保持1个糖果
2 2 2 > 0 2 评分比左边高，糖果数为左边加1

第二次遍历（从右到左）

索引 ratings[i] 比较 candies[i] 说明
2 2 - 2 最右边的孩子，保持2个糖果
1 0 0 < 2 1 评分比右边低，保持1个糖果
0 1 1 > 0 max(1, 1+1) = 2 评分比右边高，糖果数为右边加1和当前值的最大值

最终结果：[2,1,2]，总糖果数：2 + 1 + 2 = 5

上升下降序列分析表

以示例1为例：ratings = [1,0,2]

索引 ratings[i] 序列类型 当前糖果数 总糖果数 说明
0 1 初始 1 1 第一个孩子，至少有1个糖果
1 0 下降 1 2 评分下降，当前孩子1个糖果
2 2 上升 2 4 评分上升，当前孩子2个糖果

注意：这种方法的实现较为复杂，上面的分析是简化版，实际实现需要考虑更多细节。

代码实现

C# 实现

public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int[] candies = new int[n];
        
        // 初始化每个孩子至少有1个糖果
        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }
        
        // 从左到右遍历
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        // 从右到左遍历
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
            }
        }
        
        // 计算总糖果数
        int totalCandies = 0;
        for (int i = 0; i < n; i++) {
            totalCandies += candies[i];
        }
        
        return totalCandies;
    }
}

Python 实现

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n
        
        # 从左到右遍历
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        
        # 从右到左遍历
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        
        # 计算总糖果数
        return sum(candies)

C++ 实现

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candies(n, 1);
        
        // 从左到右遍历
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        // 从右到左遍历
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }
        
        // 计算总糖果数
        int totalCandies = 0;
        for (int i = 0; i < n; i++) {
            totalCandies += candies[i];
        }
        
        return totalCandies;
    }
};

执行结果

C# 实现

  • 执行用时：96 ms
  • 内存消耗：42.8 MB

Python 实现

  • 执行用时：160 ms
  • 内存消耗：17.8 MB

C++ 实现

  • 执行用时：16 ms
  • 内存消耗：17.4 MB

性能对比

语言 执行用时 内存消耗 特点
C# 96 ms 42.8 MB 执行速度适中，内存消耗较高
Python 160 ms 17.8 MB 执行速度较慢，内存消耗适中
C++ 16 ms 17.4 MB 执行速度最快，内存消耗最低

代码亮点

  1. 🎯 两次遍历解决问题，时间复杂度为O(n)
  2. 💡 巧妙利用从左到右和从右到左两次遍历，确保同时满足两个方向的要求
  3. 🔍 使用Math.Max函数确保取两次遍历结果的最大值
  4. 🎨 代码简洁清晰，逻辑易于理解

常见错误分析

  1. 🚫 只考虑从左到右的遍历，忽略了从右到左的情况
  2. 🚫 没有正确处理评分相等的情况
  3. 🚫 初始化糖果数为0，而不是1
  4. 🚫 在第二次遍历时，直接覆盖第一次遍历的结果，而不是取最大值

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
两次遍历 O(n) O(n) 思路清晰，实现简单 需要额外空间存储每个孩子的糖果数
常数空间的一次遍历 O(n) O(1) 空间复杂度低 实现复杂，不直观
贪心算法（两次遍历的变种） O(n) O(n) 思路清晰，实现简单 需要额外空间存储每个孩子的糖果数

相关题目