步骤1：计算问题性质的定义
我们需要解决的题目是一个典型的贪心算法问题，要求分发糖果的数量，满足特定条件。以下是问题的详细定义：
-
输入：
ratings：长度为n的数组，表示每个孩子的评分，1 <= n <= 2 * 10^4。- 每个孩子的评分为
0 <= ratings[i] <= 2 * 10^4。
-
输出：
- 返回满足题目条件的最少糖果数目。
-
题目条件：
- 每个孩子至少分得 1 颗糖果。
- 如果孩子
i的评分比相邻的孩子高（即ratings[i] > ratings[i-1]或ratings[i] > ratings[i+1]），那么i号孩子获得的糖果数量必须比相邻的孩子多。
边界条件：
- 当
n == 1时，孩子只有一个，只需要 1 颗糖果。 - 当所有孩子的评分相同，即
ratings[i] == ratings[j]对于所有i, j时，每个孩子都只需要 1 颗糖果。
步骤2：问题分解与算法设计
这个问题的核心是如何在保证所有孩子至少 1 颗糖果的前提下，尽量减少糖果的分配总数，并满足评分高的孩子分配更多糖果的要求。
我们可以使用贪心算法来解决这个问题，分两轮处理：
- 从左到右遍历：
- 从左向右遍历，如果孩子
i的评分高于左边孩子i-1的评分（ratings[i] > ratings[i-1]），则i号孩子的糖果数量要比i-1号孩子的多。因此，将i号孩子的糖果数设置为i-1号孩子的糖果数 +1。
- 从左向右遍历，如果孩子
- 从右到左遍历：
- 从右向左遍历，如果孩子
i的评分高于右边孩子i+1的评分（ratings[i] > ratings[i+1]），且i号孩子的糖果数不满足比i+1号孩子多的要求，则需要更新i号孩子的糖果数为i+1号孩子的糖果数 +1。
- 从右向左遍历，如果孩子
- 最终结果：
- 两轮遍历后，所有的孩子都能满足题目的糖果分配要求，最后计算糖果总数即可。
时间复杂度分析：
- 时间复杂度：每个孩子会被遍历两次，因此时间复杂度为
O(n)，其中n是孩子的数量。 - 空间复杂度：我们需要一个数组存储每个孩子的糖果数，空间复杂度为
O(n)。
步骤3：C++代码实现
代码说明：
- 初始化糖果数组
candies，每个孩子都至少分配 1 颗糖果。 - 第一轮遍历：从左到右，如果当前孩子的评分比左边孩子的评分高，则当前孩子的糖果数要比左边的孩子多。
- 第二轮遍历：从右到左，如果当前孩子的评分比右边孩子的评分高，则需要更新糖果数，保证它比右边的孩子多。
- 最后，将所有孩子的糖果数相加，得到最少需要的糖果数目。
步骤4：算法的优化与效率提升
通过这个问题的解决，我们可以看到贪心算法在局部最优解的策略下，能够快速找到全局最优解。该算法的时间复杂度为 O(n)，适合处理大规模数据集。由于题目只要求相邻两个孩子进行比较，因此不需要使用复杂的数据结构，这也是贪心算法高效的原因之一。
在处理大规模数据时，贪心算法可以减少不必要的计算量，保证在合理的时间内完成任务。该方法可以轻松扩展到更复杂的评分系统，甚至可以处理多维的分配问题。
步骤5：实际应用场景分析
这种算法可用于资源分配问题，例如在企业中对员工的绩效评估和奖金分配。假设员工根据业绩获得奖金，且相邻团队成员的业绩有明确的比较规则，我们需要确保绩效高的员工获得更多的奖金，同时每个员工至少获得一份奖金。这与本题的糖果分配问题类似。
具体实现方法：
- 员工绩效数据作为输入。
- 根据相邻员工的绩效对比，使用贪心算法分配奖金。
- 保证高绩效员工获得更多奖金，最终计算出最少的总奖金数。
通过这种方式，企业可以公平地分配资源，提升员工满意度，并确保绩效较高者得到应有的奖励。
就是说这个例子蛮贴合实际的🥹
