力扣面试经典——135题

💡 参考代码：

/**
 * @brief 计算分发糖果的最少数量
 * 
 * 根据孩子们的评分分配糖果，满足以下条件：
 * 1. 每个孩子至少分配到1个糖果
 * 2. 相邻两个孩子中，评分更高的孩子会获得更多的糖果
 * 
 * @param ratings 孩子们的评分数组
 * @param ratingsSize 评分数组的长度
 * @return int 需要准备的最少糖果数目
 * 
 * @details 算法采用两次遍历策略：
 *          1. 从左到右遍历：确保右边评分高的孩子比左边相邻孩子获得更多糖果
 *          2. 从右到左遍历：确保左边评分高的孩子比右边相邻孩子获得更多糖果
 *          时间复杂度：O(n)，空间复杂度：O(n)
 * 
 * @example 
 *          输入：ratings = [1,0,2]
 *          输出：5
 *          解释：分别给三个孩子分发2、1、2颗糖果
 * 
 * @example
 *          输入：ratings = [1,2,2]
 *          输出：4
 *          解释：分别给三个孩子分发1、2、1颗糖果
 */
int candy(int* ratings, int ratingsSize) {
    if (ratingsSize <= 1) {
        return ratingsSize;
    }
    
    // 初始化每个孩子至少1个糖果
    int* candies = (int*)calloc(ratingsSize, sizeof(int));
    for (int i = 0; i < ratingsSize; i++) {
        candies[i] = 1;
    }
    
    // 从左到右遍历：确保右边评分高的孩子比左边相邻的孩子获得更多糖果
    for (int i = 1; i < ratingsSize; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    
    // 从右到左遍历：确保左边评分高的孩子比右边相邻的孩子获得更多糖果
    for (int i = ratingsSize - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = (candies[i] > candies[i + 1] + 1) ? candies[i] : candies[i + 1] + 1;
        }
    }
    
    // 计算总糖果数
    int total = 0;
    for (int i = 0; i < ratingsSize; i++) {
        total += candies[i];
    }
    
    free(candies);
    return total;
}

📖 总结：

点击展开题目总结

🤔 分发糖果

---

1️⃣ 题目核心信息

🎯 功能描述：根据孩子们的评分分配糖果，确保每个孩子至少获得1颗糖果，且评分更高的孩子比相邻孩子获得更多糖果，求最少需要的糖果总数。

📥 输入输出：

• 输入：int* ratings - 孩子们的评分数组，int ratingsSize - 数组长度
• 输出：int - 需要准备的最少糖果数目

---

2️⃣ 实现原理

💡 核心思路：采用两次遍历的贪心算法，分别处理左右两个方向的约束关系，确保满足所有相邻比较条件。

📋 实现步骤：

1. 初始化每个孩子分配1颗糖果
2. 从左到右遍历，确保右边评分高的孩子比左边相邻孩子获得更多糖果
3. 从右到左遍历，确保左边评分高的孩子比右边相邻孩子获得更多糖果
4. 累加所有孩子的糖果数作为结果返回

---

3️⃣ 关键点解析

原始思路是单向遍历，但存在问题：只考虑了单方向的约束关系，忽略了反向也可能影响糖果分配。最优解通过两次遍历，分别处理左右两个方向的约束，确保结果正确。

🎯 代码技巧

• 使用 calloc 初始化数组，同时分配内存和置零
• 两次遍历分别处理不同方向的约束条件
• 使用三元运算符 ? : 简洁地实现 max 操作

4️⃣ 使用场景

✅ 适用情况：

• 需要满足双向相邻约束的优化问题
• 资源分配需要考虑左右邻居关系的场景
• 贪心算法中需要多轮约束满足的问题

⚠️ 前提条件：

• 输入数组不为空
• 评分值为非负整数
• 需要满足题目规定的两个分配条件

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n) - 需要三次遍历数组（初始化一次，左右遍历各一次）

• 💾 空间复杂度：O(n) - 需要额外数组存储每个孩子的糖果数

6️⃣ 注意事项

🚩 边界情况：

• 空数组或只有一个孩子的情况
• 所有孩子评分相同的情况
• 评分严格递增或递减的情况

💥 易错点：

• 只进行单向遍历，忽略反向约束关系
• 错误使用 memset 给 int 数组赋值为1
• 在更新糖果数时没有取最大值，导致不满足约束条件

加载评论中...