[LeetCode] 每日一题 135. 分发糖果（贪心算法）

题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。

• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

题目链接

https://leetcode.cn/problems/candy

示例输入

示例 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 * 10^4

• 0 <= ratings[i] <= 2 * 10^4

解题思路

这题和昨天的“分糖果”题目名字类似，但本质完全不同。我们不再是根据某些连续递增序列来一次性分配，而是要满足每个孩子都比邻近评分低的孩子分得少糖果这一点。显然这是一个局部最优推动全局最优的典型贪心问题。

为了满足题目中“相邻孩子评分更高的孩子要分更多糖果”的要求，我们从两个方向来思考：

1. 从左往右遍历，保证每个孩子如果比左边评分高，就要比左边孩子多分一个糖果

2. 从右往左遍历，保证每个孩子如果比右边评分高，也要比右边孩子多分一个糖果

分别维护两个数组 left 和 right，用于记录两个方向上每个孩子“单方面”满足规则所需要的最少糖果数。最终我们取每个孩子在两个数组中对应位置的最大值，即为该孩子最终需要的糖果数量。为了优化遍历次数，我们可以在第二次遍历（从右往左）时顺便将结果累计起来。

注意⚠️：右向遍历中我们没有累加最右边孩子的糖果数量，因此初始化时要先将其加到 ans 中

代码实现

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        int ans = left[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
            ans += Math.max(left[i], right[i]);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：

  • O(n) ，只遍历了两次数组

• 空间复杂度：

  • O(n) ，用了两个额外的数组分别存储左右遍历结果

总结

这道题巧妙运用了贪心思想+双向遍历的方式，分别从两个方向维护“局部最优”，再在最后整合结果。这种“先分别满足一边，再合并”是贪心解题中的一种经典套路👍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。