题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
2023年5月
class Solution {
public:
int candy(vector& ratings) {
m_c = ratings.size();
std::vector<pair<int, int>> vValueIndexs;
for (int i = 0; i < m_c; i++)
{
vValueIndexs.emplace_back(ratings[i], i);
}
sort(vValueIndexs.begin(), vValueIndexs.end());
vector vRet(m_c);
for (int j = 0; j < vValueIndexs.size(); j++)
{
const int iCur = vValueIndexs[j].first;
const int i = vValueIndexs[j].second;
int num = 1;
if ((i + 1 < m_c) && (ratings[i + 1] < iCur))
{
num = max(num, vRet[i + 1]+1);
}
if ((i > 0) && (ratings[i - 1] < iCur))
{
num = max(num, vRet[i - 1]+1);
}
vRet[i] = num;
}
return std::accumulate(vRet.begin(), vRet.end(), 0);
}
int m_c;
};2023年8月
class Solution {
public:
int candy(vector& ratings) {
m_c = ratings.size();
std::vector<pair<int, int>> vValueIndexs;
for (int i = 0; i < m_c; i++)
{
vValueIndexs.emplace_back(ratings[i], i);
}
sort(vValueIndexs.begin(), vValueIndexs.end());
vector vRet(m_c);
for (int j = 0; j < vValueIndexs.size(); j++)
{
const int iCur = vValueIndexs[j].first;
const int i = vValueIndexs[j].second;
int num = 1;
if ((i + 1 < m_c) && (ratings[i + 1] < iCur))
{
num = max(num, vRet[i + 1]+1);
}
if ((i > 0) && (ratings[i - 1] < iCur))
{
num = max(num, vRet[i - 1]+1);
}
vRet[i] = num;
}
return std::accumulate(vRet.begin(), vRet.end(), 0);
}
int m_c;
};其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
我的其它课程
[]
()
测试环境
win7 VS2019 C++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版