力扣135分发糖果：代码随想录Day 29，掌握贪心算法的精髓

在算法学习过程中力扣LeetCode的135题“分发糖果”是一个经典的题目它考察了我们对于贪心算法的理解和运用。 这道题目源自实际应用场景例如在团队绩效考核中我们需要根据员工的表现来分配奖励。代码随想录day 29就着重讲解了如何用贪心算法巧妙地解决这个问题。题目描述老师想给孩子们分发糖果每人至少一个糖果。 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。 给定一个数组ratings代表每个孩子的评分。 你需要最小化糖果的总数。为什么选择贪心算法为什么可以使用贪心算法解决这个问题呢 贪心算法的核心思想是每一步都选择当前最优的策略最终达到全局最优。 在这个问题中我们可以分别从左到右和从右到左遍历数组保证每个方向上评分更高的孩子都比邻居得到更多的糖果。 这种局部最优的策略最终可以保证糖果总数最少从而达到全局最优。代码实现与详细分析解决力扣 135.分发糖果问题需要两次遍历确保同时满足左右规则下面提供 C 代码示例并附带详细注释。C 代码实现#include iostream#include vector#include numeric // 使用 std::accumulate 计算总和using namespace std;int candy(vectorint ratings) { int n ratings.size(); vectorint candies(n, 1); // 初始化每个孩子至少一个糖果 // 从左向右遍历如果右边的孩子评分更高则糖果数加1 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { candies[i] candies[i - 1] 1; } } // 从右向左遍历如果左边的孩子评分更高且糖果数不比右边多则更新糖果数 for (int i n - 2; i 0; --i) { if (ratings[i] ratings[i 1]) { candies[i] max(candies[i], candies[i 1] 1); // 取最大值保证满足左右规则 } } // 计算糖果总数 return accumulate(candies.begin(), candies.end(), 0); // 使用 accumulate 方便求和}int main() { vectorint ratings {1, 0, 2}; cout 需要的最少糖果数: candy(ratings) endl; // 输出: 5 ratings {1, 2, 2}; cout 需要的最少糖果数: candy(ratings) endl; // 输出: 4 return 0;}代码解读初始化首先创建一个与ratings数组大小相同的candies数组初始化每个元素为1表示每个孩子至少分得一个糖果。从左向右遍历从第二个孩子开始如果当前孩子的评分高于前一个孩子则当前孩子的糖果数在前一个孩子的基础上加1。从右向左遍历从倒数第二个孩子开始如果当前孩子的评分高于后一个孩子则需要比较当前孩子的糖果数和后一个孩子的糖果数加1取较大值。 这一步是关键确保同时满足左右规则。计算总和使用std::accumulate函数计算candies数组的总和即为最少需要的糖果数。复杂度分析时间复杂度O(n)需要两次遍历数组。空间复杂度O(n)需要额外的candies数组存储每个孩子的糖果数。避坑指南与实战经验在解决代码随想录day 29分发糖果问题时需要注意以下几点注意边界条件当数组为空或者只有一个元素时需要进行特殊处理避免出现数组越界等问题。理解贪心策略理解贪心算法的本质是解决问题的关键。 在这个问题中贪心策略体现在每次都保证局部最优最终达到全局最优。 错误的贪心策略可能导致无法得到正确的结果。优化空间复杂度虽然 O(n) 的空间复杂度是可以接受的但在某些情况下我们可以尝试优化空间复杂度。 例如可以使用两个变量分别记录从左向右和从右向左遍历时的糖果数从而减少额外的空间开销。 但这种优化会使代码可读性降低需要权衡利弊。调试技巧在调试代码时可以使用一些测试用例来验证代码的正确性。 例如可以构造一些特殊情况的测试用例例如数组中所有元素都相等、数组已经排序等来检查代码是否存在bug。通过对力扣 135.分发糖果问题的深入分析和代码实践我们可以更好地理解贪心算法的思想并将其应用到其他类似的问题中。 在实际工作中我们可以借鉴这种解决问题的思路将复杂的问题分解为多个简单的子问题然后使用贪心算法或其他算法来逐个解决最终达到整体最优的目标。相关阅读从源代码构建编译sfml库的视频教程所需信息Redis的零食盒满了怎么办详解缓存淘汰策略【文星索引】搜索引擎项目测试报告【算法】小点List.removejava基础-10 : API--- 常见排序算法汇总 ---