218.贪心算法：分发糖果（力扣）
核心思想
- 初始化每个学生的糖果数为1：
- 确保每个学生至少有一颗糖果。
- 从左到右遍历：
- 如果当前学生的评分高于前一个学生，则当前学生的糖果数应比前一个学生多一颗。
- 从右到左遍历：
- 如果当前学生的评分高于后一个学生，则当前学生的糖果数应比后一个学生多一颗。
- 同时确保当前学生的糖果数不小于先前分配的糖果数（在从左到右遍历时确定的）。
- 计算糖果总数：
- 累加每个学生的糖果数，得到最终的总数。
代码解决
class Solution {
public:int candy(vector<int>& ratings) {int result = 0;vector<int> candyNum(ratings.size(), 1); // 初始化每个学生的糖果数为1// 从左到右遍历，确保评分高的学生比前一个学生得到更多的糖果for (int i = 1; i < ratings.size(); i++){if (ratings[i] > ratings[i - 1]){candyNum[i] = candyNum[i - 1] + 1;}}// 从右到左遍历，确保评分高的学生比后一个学生得到更多的糖果for (int i = ratings.size() - 2; i >= 0; i--){if (ratings[i] > ratings[i + 1]){candyNum[i] = max(candyNum[i + 1] + 1, candyNum[i]);}}// 计算糖果总数for (int num : candyNum){result += num;}return result;}
};
这段代码是一个名为`Solution`的类中的一个成员函数，其功能是计算一个整数数组`ratings`中的孩子根据他们的评分需要分配的最少糖果数量。具体处理方式如下：
1. 函数声明为`int candy(vector<int>& ratings)`，表示该函数接受一个整数向量`ratings`作为参数，并返回一个整数值。
2. `int result=0;`初始化一个名为`result`的整数变量，用于存储最终的结果，即所有孩子所需的最少糖果总数。
3. `vector<int> candyNum(ratings.size(),1);`创建一个名为`candyNum`的整数向量，其大小与`ratings`相同，并将所有元素初始化为1。这个向量用于存储每个孩子分配到的糖果数量。
4. 第一个for循环`for(int i=1;i<ratings.size();i++)`从索引1开始遍历`ratings`数组，直到数组末尾。在这个循环中，如果当前孩子的评分比他前一个孩子的评分高（`ratings[i]>ratings[i-1]`），则当前孩子的糖果数应该比前一个孩子的糖果数多1（`candyNum[i]=candyNum[i-1]+1;`）。
5. 第二个for循环`for(int i=ratings.size()-2;i>=0;i--)`从数组倒数第二个元素开始向前遍历，直到数组开头。在这个循环中，如果当前孩子的评分比他后一个孩子的评分高（`ratings[i]>ratings[i+1]`），则当前孩子的糖果数应该是他后一个孩子的糖果数加1和他当前糖果数中的较大值（`candyNum[i]=max(candyNum[i+1]+1,candyNum[i]);`）。
6. 第三个for循环`for(int num:candyNum)`遍历`candyNum`向量中的每个元素，将它们累加到`result`变量中，从而计算出所有孩子所需的最少糖果总数。
7. 最后，函数返回`result`变量的值，即所有孩子所需的最少糖果总数。
总结来说，这个函数通过两次遍历和比较相邻孩子的评分来确定每个孩子应该分配到的最少糖果数，然后计算总和得到结果。这种算法确保了评分较高的孩子会得到更多的糖果，并且满足相邻孩子评分差异较大的孩子也会获得额外的糖果。