题目
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; };
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
[https://edu.csdn.net/lecturer/6176]
(https://edu.csdn.net/lecturer/6176)
测试环境
win7 VS2019 C++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
