分发糖果——使用贪心算法

135. 分发糖果

已解答

困难

相关标签

相关企业

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

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

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

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

示例 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 * 104
• 0 <= ratings[i] <= 2 * 104

这个算法不太容易想到，我一开始是两边都照顾，导致无法正确地执行这个算法。但是，看了解析了才明白，贪心在先从前往后，然后在从后往前

要考虑的情况：

1.当前孩子的评分与前一个孩子的评分比较，以确定是否应该增加当前孩子的糖果数量。
2.当前孩子的评分与后一个孩子的评分比较，以确定是否应该增加当前孩子的糖果数量。

因此，先从前往后，然后在从后往前看。

执行用时分布

3ms

击败99.88%使用 C++ 的用户

消耗内存分布

19.68MB

击败35.53%使用 C++ 的用户

11ms21ms32ms42ms53ms63ms74ms0%5%10%15%

11ms21ms32ms42ms53ms63ms74ms

代码C++

class Solution {
public:
    int candy(vector<int>& ratings) {
        
        int sum =0;
        int size =ratings.size();
        
        vector<int> vec(size, 1); 
        
        for(int i =1;i<size;i++){
            if(ratings[i-1]<ratings[i]){
                vec[i]=vec[i-1]+1;
        }}
        for(int k =size-2;k>=0;k--){
            if(ratings[k]>ratings[k+1]){
                vec[k] = max(vec[k],vec[k+1]+1);
            }
        }
        for(auto it : vec){
            sum += it;
        }
        return sum;
    }
};