分发糖果链接题目链接：https://leetcode-cn.com/problems/candy老师要给孩子们分发糖果。有N个孩子站成一条直线。老师会根据每个孩子的表现，给他们打分。你需要帮助老师按照以下要求给这些孩子分发糖果：每个孩子至少分到1颗糖果。在相邻的孩子中，得分最高的孩子必须得到更多的糖果。那么老师至少需要准备多少颗糖果呢？示例1：输入：[1,0,2]输出：5解释：你可以分别给这三个孩子分发2、1、2颗糖果。示例2：输入：[1,2,2]输出：4解释：你可以分别给这三个孩子分发1、2、1颗糖果。第三个孩子只得到1颗糖果，满足了以上两个条件。这道题的思路一定是一边确定后，再确定另一边。比如比较每个孩子的左边，再比较右边。如果你同时考虑双方，你就会忽视对方。先判断右边分数大于左边分数的情况（即从前向后遍历）。此时局部最优：只要右边的分数大于左边的分数，右边的孩子就多吃一颗糖。全局最优：在相邻的孩子中，得分最高的孩子右边的孩子比左边的孩子得到更多的糖果。局部最优可以导致全局最优。如果ratings[i]>ratings[i-1]那么[i]肯定比[i-1]多一颗糖，所以贪心：candyVec[i]=candyVec[i-1]+1代码如下：//从前到后for(inti=1;iratings[i-1])candyVec[i]=candyVec[i-1]+1;}如图：分发糖果，然后判断左孩子大于右孩子的情况（从后往前遍历）。这里可能有同学会有疑惑，为什么不能从前向后遍历呢？因为如果从前向后遍历，根据ratings[i+1]来确定ratings[i]对应的糖果，那么每次都不能用之前的比较结果。所以确定左孩子大于右孩子一定要从后往前遍历！如果ratings[i]>ratings[i+1]，那么candyVec[i]（第i个孩子的糖果数量）有两种选择，一种是candyVec[i+1]+1（糖果数量右加1得到），另一个是candyVec[i]（右孩子大于左孩子时得到的糖果数）。那我们又要贪心了，局部最优：取candyVec[i+1]+1和candyVec[i]最大数量的糖果，保证第i个孩子的糖果数量大于左边和正确的。全局最优：在相邻的孩子中，分数越高的孩子得到的糖果越多。局部最优可以导致全局最优。所以取糖果数量最多的candyVec[i+1]+1和candyVec[i]。CandyVec[i]只取最大的糖果，以保持左边candyVec[i-1]的糖果比右边的candyVec[i]+1]多的糖果。如图：分发糖果1，所以流程代码如下：//从后往前for(inti=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candyVec[i]=max(candyVec[i],candyVec[i+1]+1);}}整体代码如下：classSolution{public:intcandy(vector&ratings){vectorcandyVec(ratings.size(),1);//从前到后for(inti=1;iratings[i-1])candyVec[i]=candyVec[i-1]+1;}//从后往前for(inti=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candyVec[i]=max(candyVec[i],candyVec[i+1]+1);}}//统计结果intresult=0;for(inti=0;i
