leetcode-135.分发糖果（Hard）（贪心算法Part2）

题目：

n 个孩子站成一排。

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

你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。

相邻两个孩子评分更高的孩子会获得更多的糖果。

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

示例1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例2:

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

分析：

不是所有的贪心算法类都需要排序。

本题中只需要简单前后两次遍历即可，时间复杂度为O（n）。

先初始化所有的孩子糖果为1：1：1
第一遍从前到后遍历。

若右边比左边的孩子评分高，则右边孩子糖果数=左边孩子糖果数+1
第二遍从后向前遍历。

若左边孩子比右边孩子评分高，且左边孩子糖果数不大于右边孩子糖果数时，则左边孩子糖果数=右边孩子糖果数+1。

本题的贪心策略为先解决临近的两个孩子的糖果数量，继而全局最优。

Code：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int length = ratings.size();
        if(length<2){
            return length;
        }
        //初始化can数组时，数组长度是length，初始化数组内所有的值为1
        vector<int> can(length,1);  
        //left to right
        for(int i=0;i<(length-1);++i){
            if(ratings[i]<ratings[i+1]){
                can[i+1] = can[i] + 1;
            }
        }
        //right to left
        for(int j=(length-1);j>0;--j){
            if(ratings[j]<ratings[j-1]){
                can[j-1] = max(can[j-1],can[j]+1);
            }
        }
        return accumulate(can.begin(),can.end(),0); 	//第一二个参数是累加范围，第三个参数是从几开始累加
    }
};

tips：

人生活的全部由两个圈子组成，一个是关注圈，一个是影响圈。

（摘自《高效人士的七个习惯》）
关注圈是你所关注的那些但是不能被你改变的事情。

比如：明星八卦，国际战争，短视频。

影响圈是你能通过自己间接或直接进行改变的事情。

比如：思考一道算法题，看两遍JVM的GC机制。

这两个圈不应该同样大小，也不应该关注圈大于影响圈。

我们应该多去关注自己，把影响圈扩大。