在这个循环中，如果当前孩子的评分比他后一个孩子的评分高（`ratings[i]>ratings[i+1]`），则当前孩子的糖果数应该是他后一个孩子的糖果数加1和他当前糖果数中的较大值（`candyNum[i]=max(candyNum[i+1]+1,candyNum[i]);在这个循环中，如果当前孩子的评分比他前一个孩子的评分高（`ratings[i]>ratings[i-1]`），则当前孩子的糖果数应该比前一个孩子的糖果数多1（`candyNum[i]=candyNum[i-1]+1;
核心思想
- 初始化每个学生的糖果数为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;
}
};
相关文章:
-
-
算法学习6——贪心算法
贪心算法是一种在每一步选择中都采取当前状态下最优或最有利的选择的算法。其核心思想是通过一系列局部最优选择来达到全局最优解。贪心算法广泛应用于各种优化问题，如最短...
[阅读全文]
-
-
-
链表是一种线性数据结构，由一系列节点组成。数据域（Data）：存储节点的数据。指针域（Pointer）：存储指向下一个节点的地址。链表的第一个节点称为头节点（Head），最后一个节…
-
链表是通过一组任意的储存单元来存储线性表中的数据元素。为建立线性关系，每个结点需要一个指针域以及指向下一结点的指针域。带头结点链表头节点不存储数据。…
版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2386932994@qq.com 举报，一经查实将立刻删除。
我要评论
发表评论