How does the greedy approach work in the Candy problem?

The greedy approach works by allocating one candy per child, then adjusting the candy counts based on ratings in two passes: left-to-right and right-to-left.

What are common pitfalls when solving the Candy problem?

Common pitfalls include missing the right-to-left pass, failing to correctly handle the candy initialization, and not accounting for edge cases like equal ratings.

Can this problem be solved with a dynamic programming approach?

While dynamic programming could solve this problem, the greedy approach is more optimal in terms of both time and space complexity.

What are the time and space complexities for the Candy problem?

The time complexity is O(n), and the space complexity is O(n), where n is the number of children in the ratings array.

What is the key invariant used in the Candy problem?

The key invariant is that a child with a higher rating than their neighbors must receive more candies, and the greedy approach ensures this is respected in two passes.

#135

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻两个孩子中，评分更高的那个会获得更多的糖果。请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。示例 1：输入： ratings…

数组贪心

题目描述

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

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

每个孩子至少分配到 1 个糖果。
相邻两个孩子中，评分更高的那个会获得更多的糖果。

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

示例 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⁴
0 <= ratings[i] <= 2 * 10⁴

lightbulb

解题思路

方法一：两次遍历

我们初始化两个数组 $left$ 和 $right$ ，其中 $left[i]$ 表示当前孩子比左边孩子评分高时，当前孩子至少应该获得的糖果数，而 $right[i]$ 表示当前孩子比右边孩子评分高时，当前孩子至少应该获得的糖果数。初始时 $left[i]=1$ , $right[i]=1$ 。

我们从左到右遍历一遍，如果当前孩子比左边孩子评分高，则 $left[i]=left[i-1]+1$ ；同理，我们从右到左遍历一遍，如果当前孩子比右边孩子评分高，则 $right[i]=right[i+1]+1$ 。

最后，我们遍历一遍评分数组，每个孩子至少应该获得的糖果数为 $left[i]$ 和 $right[i]$ 中的最大值，将它们累加起来即为答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是评分数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
        return sum(max(a, b) for a, b in zip(left, right))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a clear understanding of greedy algorithms and how to implement the left-to-right and right-to-left passes.
question_mark
Test the candidate’s ability to minimize the number of candies through an optimal distribution while respecting the invariant.
question_mark
Expect the candidate to handle edge cases such as consecutive children with equal ratings or large arrays efficiently.

warning

常见陷阱

外企场景

error
Failing to correctly handle the right-to-left pass, potentially leading to incorrect candy assignments.
error
Not initializing candies properly or misunderstanding the invariant conditions for rating comparisons.
error
Omitting edge cases, such as when all ratings are equal or when there's only one child.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem by requiring the solution to work for multiple test cases.
arrow_right_alt
Modify the problem to allow varying minimum candy distributions, such as children with ratings greater than 5.
arrow_right_alt
Increase the constraints by considering very large input sizes, testing the efficiency of the algorithm further.

help

常见问题

外企场景

继续练习

#134 加油站 #122 买卖股票的最佳时机 II #179 最大数