【算法基础】贪心算法 LeetCode 135. 分发糖果

分发糖果

题目介绍

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

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

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

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

测试用例

算法思想：

分发糖果是贪心算法思想的典型例题。根据题意我们可以进行如下解读。分发糖果的要求就只有两个。首先是每个孩子至少分配到一个糖果。那么我们在初始化答案数组的时候是需要将初始化的值全部初始化为1。其次第二要求是相邻两个孩子评分更高的孩子会获得更多的糖果。那么相邻之间如何判断，我们可以通过测试用例发现就是第i位的糖果个数受左右两边的影响。所以肯定是不能在一次遍历就能将所以情况进行判断处理。所以和前缀和的思想差不多的，正反都进行一次遍历将所有情况取最大值，那么就是我们需要分发的糖果。

为什么是正反都进行一次遍历判断呢？

首先我们进行正向遍历的时候，判断如果右边ratings[i]>rating[i-1]那么，v[i]=v[i-1]+1，这里是符合分发要求的，与此同时这个肯定也是不全面的，会漏掉，左边比右边大情况，答案数组没有+1进行更新。

然后我们进行反向的遍历，解决 1比0大 却分发的糖果数都是1，还有最后4，3，2的不符合分发糖果要求的情况。

源代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        //正反都遍历一遍
        vector<int> v(ratings.size(),1);
        for(int i=1;i<ratings.size();i++)
        {
            if(ratings[i]>ratings[i-1])
            {
                v[i]=v[i-1]+1;
            }
        }
        //反过来
        for(int i=ratings.size()-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1])
            {
                v[i]=max(v[i+1]+1,v[i]);
            }
        }
        int sum=0;
        for(auto x:v)
        {
            sum+=x;
        }
        return sum;
    }
};