leetcode 135. 分发糖果

问题分析

LeetCode 135题“分发糖果”要求给一排孩子分发糖果，每个孩子至少得到1个糖果，且相邻孩子中评分高的孩子必须获得更多糖果，求最少需要多少糖果。

解题思路

这个问题可以通过两次遍历的贪心算法来解决：

1. 第一次从左到右遍历：确保每个孩子如果比左边孩子评分高，则获得更多糖果。
2. 第二次从右到左遍历：确保每个孩子如果比右边孩子评分高，则获得更多糖果。

这种方法保证了每个孩子与相邻孩子的比较条件都被满足，同时使用最少的糖果数。

代码实现

下面是使用C++实现的代码：

#include <vector>
using namespace std;

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if (n <= 1) return n;
        
        // 初始化每个孩子至少有1个糖果
        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 total = 0;
        for (int candy : candies) {
            total += candy;
        }
        
        return total;
    }
};

题目

https://leetcode.cn/problems/candy/solutions/533150/fen-fa-tang-guo-by-leetcode-solution-f01p/?envType=study-plan-v2&envId=selected-coding-interview

代码解释

1. 初始化糖果数组：

   • 创建一个长度为n的数组candies，初始值都为1，表示每个孩子至少有1个糖果。

2. 第一次遍历（从左到右）：

   • 从第二个孩子开始，如果当前孩子评分高于前一个孩子，则当前孩子的糖果数为前一个孩子的糖果数加1。

3. 第二次遍历（从右到左）：

   • 从倒数第二个孩子开始，如果当前孩子评分高于后一个孩子，则当前孩子的糖果数取candies[i]和candies[i+1]+1中的较大值。
   • 这确保了当前孩子的糖果数同时满足左右两个方向的比较条件。

4. 计算总糖果数：

   • 遍历糖果数组，累加所有糖果数得到结果。

复杂度分析

• 时间复杂度：O(n)，其中n是孩子的数量。需要遍历数组两次。
• 空间复杂度：O(n)，需要额外的数组来存储每个孩子的糖果数。

这种方法通过两次遍历，巧妙地解决了相邻孩子之间的比较关系，确保了使用最少的糖果数。