贪心
解题思路
两次贪心的策略（如果存在多个维度，则要一个维度一个维度去考虑）：
- 一次是从左到右遍历，只比较右边孩子评分比左边大的情况；
- 一次是从右到左遍历，只比较左边孩子评分比右边大的情况；
局部最优：只要右边评分比左边大，右边的孩子就多一个糖果；
全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果；
具体步骤：
- 由题目可知 每个孩子至少分配到 1 个糖果，则先给每个孩子一个糖果；
- 由题目可知 相邻两个孩子评分更高的孩子会获得更多的糖果，从左到右遍历，只比较右边孩子评分比左边大的情况；
- 从右到左遍历，只比较左边孩子评分比右边大的情况；
- 然后对两次比较情况取最大值即可，返回糖果的总和；
复杂度
-
时间复杂度：
O(N)，遍历两遍数组即可得到结果； -
空间复杂度：
O(N)，需要借用 left、right 的线性额外空间；
代码实现
var candy = function (ratings) {
// 1. 先给每个孩子一个糖果
let candys = new Array(ratings.length).fill(1);
// 2. 从左到右遍历，只比较右边孩子评分比左边大的情况
for (let i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candys[i] = candys[i - 1] + 1;
}
}
// 3. 从右到左遍历，只比较左边孩子评分比右边大的情况
for (let i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candys[i] = Math.max(candys[i], candys[i + 1] + 1);
}
}
// 4. 求和计算出最少需要多少糖果
return candys.reduce((a, b) => a + b);
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 134. 加油站
上一篇
评论
