What is the main approach to solve Maximum Candies You Can Get from Boxes?

Use a breadth-first search (BFS) to explore all boxes you can access, collecting candies and keys in order of availability.

Can DFS be used instead of BFS?

DFS can work but may fail to process boxes in the correct order to use keys effectively; BFS ensures layer-by-layer access.

How do I track which boxes have been opened?

Maintain a visited set to mark boxes as processed, preventing counting the same candies multiple times.

What should I do with keys found in a box?

Add keys to a map or set and enqueue corresponding locked boxes for BFS once the keys are obtained.

What pattern does this problem exemplify?

This problem is a graph traversal pattern using BFS, where nodes are boxes and edges represent access via keys or containment.

#1298

Hard

auto_awesome图·搜索

LeetCode 题解工作台

你能从盒子里获得的最大糖果数

给你 n 个盒子，每个盒子的格式为 [status, candies, keys, containedBoxes] ，其中：状态字 status[i] ：整数，如果 box[i] 是开的，那么是 1 ，否则是 0 。糖果数 candies[i] : 整数，表示 box[i] 中糖果的数目。钥匙…

数组广度优先搜索图

题目描述

给你 n 个盒子，每个盒子的格式为 [status, candies, keys, containedBoxes] ，其中：

状态字 status[i]：整数，如果 box[i] 是开的，那么是 1 ，否则是 0 。
糖果数 candies[i]: 整数，表示 box[i] 中糖果的数目。
钥匙 keys[i]：数组，表示你打开 box[i] 后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。
内含的盒子 containedBoxes[i]：整数，表示放在 box[i] 里的盒子所对应的下标。

给你一个整数数组 initialBoxes，包含你最初拥有的盒子。你可以拿走每个 已打开盒子 里的所有糖果，并且可以使用其中的钥匙去开启新的盒子，并且可以使用在其中发现的其他盒子。

请你按照上述规则，返回可以获得糖果的 最大数目 。

示例 1：

输入：status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
输出：16
解释：
一开始你有盒子 0 。你将获得它里面的 7 个糖果和盒子 1 和 2。
盒子 1 目前状态是关闭的，而且你还没有对应它的钥匙。所以你将会打开盒子 2 ，并得到里面的 4 个糖果和盒子 1 的钥匙。
在盒子 1 中，你会获得 5 个糖果和盒子 3 ，但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。
你总共可以获得的糖果数目 = 7 + 4 + 5 = 16 个。

示例 2：

输入：status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
输出：6
解释：
你一开始拥有盒子 0 。打开它你可以找到盒子 1,2,3,4,5 和它们对应的钥匙。
打开这些盒子，你将获得所有盒子的糖果，所以总糖果数为 6 个。

示例 3：

输入：status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]
输出：1

示例 4：

输入：status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []
输出：0

示例 5：

输入：status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
输出：7

提示：

1 <= status.length <= 1000
status.length == candies.length == keys.length == containedBoxes.length == n
status[i] 要么是 0 要么是 1 。
1 <= candies[i] <= 1000
0 <= keys[i].length <= status.length
0 <= keys[i][j] < status.length
keys[i] 中的值都是互不相同的。
0 <= containedBoxes[i].length <= status.length
0 <= containedBoxes[i][j] < status.length
containedBoxes[i] 中的值都是互不相同的。
每个盒子最多被一个盒子包含。
0 <= initialBoxes.length <= status.length
0 <= initialBoxes[i] < status.length

lightbulb

解题思路

方法一：BFS + 哈希集合

题目给定一批盒子，每个盒子可能有状态（开/关）、糖果、钥匙、以及其他盒子。我们的目标是通过初始给定的一些盒子，尽可能多地打开更多盒子，并收集其中的糖果。可以通过获得钥匙来解锁新盒子，通过盒子中嵌套的盒子来获取更多资源。

我们采用 BFS 的方式模拟整个探索过程。

我们用一个队列 $q$ 表示当前可以访问的、已经开启 的盒子；用两个集合 $\textit{has}$ 和 $\textit{took}$ 分别记录我们拥有的所有盒子和已经处理过的盒子，防止重复。

初始时，将所有 $\textit{initialBoxes}$ 添加到 $\textit{has}$ 中，如果初始盒子状态为开启，立即加入队列 $\textit{q}$ 并累计糖果；

然后进行 BFS，依次从 $\textit{q}$ 中取出盒子：

获取盒子中的钥匙 $\textit{keys[box]}$ ，将能解锁的盒子加入队列；
收集盒子中包含的其他盒子 $\textit{containedBoxes[box]}$ ，如果状态是开启的且未处理过，则立即处理；

每个盒子最多处理一次，糖果累计一次，最终返回总糖果数 $\textit{ans}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ，其中 $n$ 是盒子的总数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

class Solution:
    def maxCandies(
        self,
        status: List[int],
        candies: List[int],
        keys: List[List[int]],
        containedBoxes: List[List[int]],
        initialBoxes: List[int],
    ) -> int:
        q = deque()
        has, took = set(initialBoxes), set()
        ans = 0

        for box in initialBoxes:
            if status[box]:
                q.append(box)
                took.add(box)
                ans += candies[box]
        while q:
            box = q.popleft()
            for k in keys[box]:
                if not status[k]:
                    status[k] = 1
                    if k in has and k not in took:
                        q.append(k)
                        took.add(k)
                        ans += candies[k]

            for b in containedBoxes[box]:
                has.add(b)
                if status[b] and b not in took:
                    q.append(b)
                    took.add(b)
                    ans += candies[b]
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^2) because each box may contain keys or boxes leading to nested processing, while space complexity is O(n) to store the visited set, queue, and auxiliary structures for BFS.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Check if candidate correctly enqueues boxes only when accessible.
question_mark
Verify they track visited boxes to avoid double counting.
question_mark
Listen for discussion on BFS versus DFS and reasoning for layer-by-layer exploration.

warning

常见陷阱

外企场景

error
Forgetting to mark boxes as visited after processing, causing overcounting.
error
Trying DFS instead of BFS and missing boxes that require keys found later.
error
Incorrectly handling boxes inside boxes without checking if the key is available.

swap_horiz

进阶变体

外企场景

arrow_right_alt
All boxes initially open, emphasizing simple BFS traversal.
arrow_right_alt
Boxes contain keys but no nested boxes, focusing on key handling logic.
arrow_right_alt
Some boxes require multiple keys, testing BFS queuing order and tracking.

help

常见问题

外企场景

继续练习

#1311 获取你好友已观看的视频 #1368 使网格图至少有一条有效路径的最小代价 #928 尽量减少恶意软件的传播 II