js-leetcode题解之135-candy.js

在JavaScript中解决LeetCode第135题《Candy》的方法涉及到利用贪心算法解决分配问题。LeetCode是一个在线编程问题平台，135题《Candy》是一个关于评分与分配的算法问题，要求给孩子们分配糖果，使得每个孩子至少得到一颗糖果，并且满足以下条件： 1. 每个孩子至少有一颗糖果。 2. 如果一个孩子的评分比旁边的孩子高，则这个孩子应比他旁边的高分孩子多得一颗糖果。 题目的难点在于如何高效地分配糖果以满足上述条件，同时保证总的糖果数尽可能少。贪心算法是解决这类问题的常用策略，核心思想是局部最优解可以构成全局最优解。 解题步骤大致如下： 1. 初始化一个数组，长度与孩子们的评分数组相同，用来记录每个孩子应得的糖果数量，初始值均为1。 2. 从左向右遍历评分数组，如果当前孩子评分比左边的孩子高，则当前孩子的糖果数应比左边孩子的糖果数多一颗。 3. 再从右向左遍历评分数组，如果当前孩子评分比右边的孩子高，则当前孩子的糖果数应比右边孩子的糖果数多一颗，但这里需要处理一个特殊情况，即如果右边孩子的糖果数已经比当前孩子多，那么当前孩子的糖果数应更新为右边孩子的糖果数加一。 4. 计算所有孩子糖果数的总和，即为需要的最少糖果数。 上述算法的时间复杂度是O(n)，因为只需要遍历两次评分数组，空间复杂度也是O(n)，需要一个额外的数组来记录每个孩子应得的糖果数。这个解法的核心在于从左到右保证了所有孩子左边的排名高的孩子都有更多糖果，从右到左保证了所有孩子右边的排名高的孩子都有更多糖果，这样就能保证每个孩子都尽量多地和两边的孩子保持公平，从而达到最优解。 此外，解题过程中需要注意边界条件处理，例如数组的第一个和最后一个孩子只有一侧可以比较，所以需要单独考虑。 利用贪心算法解决这类评分分配问题，通过两遍遍历评分数组，并适当更新每个孩子应得的糖果数，可以有效地解决LeetCode第135题《Candy》。