点击获取AI摘要

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

给你 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

问题分析

给定 nn 个盒子，每个盒子 ii 包含以下属性：

  • status[i]：整数，若盒子已开则为 1，否则为 0（表示锁着，需要钥匙）。
  • candies[i]：整数，表示盒子中糖果数量。
  • keys[i]：数组，打开盒子 ii 后可获得的一组钥匙（每个元素为另一个盒子的下标）。
  • containedBoxes[i]：数组，打开盒子 ii 后可获得的一组盒子（这些盒子可继续尝试打开）。
  • initialBoxes：初始时手中已有的盒子列表。

我们的目标是在合法操作（只能打开当前已拥有且已开或已有钥匙的盒子）下，获取的糖果总数最大化。

整个人物过程类似图的 BFS 遍历：

  1. 拥有盒子 → 检查是否可打开 → 若可打开，则取糖果并获取钥匙与新盒子 → 用新钥匙尝试打开原先无法打开的盒子 → 重复直至无可打开盒子。
  2. 核心需要跟踪的三种状态：
    • 已拥有盒子：有哪些盒子“在手”但可能还没打开。
    • 已获得钥匙：有哪些盒子对应的钥匙已经在手。
    • 已打开盒子：哪些盒子已经被打开并取过糖果，避免重复计数。

算法思路

  1. 数据结构准备

    • 用 have_box = set(initialBoxes) 记录当前“已拥有但未必打开”的盒子下标集合。
    • 用 have_key = set() 记录当前已有的所有钥匙下标。
    • 用 opened = [False] * n 标记每个盒子是否已打开过并取过糖果。
    • 用 waiting = set() 记录“已拥有但因没有钥匙暂时无法打开”的盒子下标。
    • 用双端队列 dq = deque() 记录“当前可打开并待处理”的盒子下标。
    • 用变量 ans = 0 累加已取的糖果总数。

  2. 初始化

    1
    2
    3
    4
    5
    for b in initialBoxes:
        if status[b] == 1:
            dq.append(b)
        else:
            waiting.add(b)
    • 若初始盒子本身已开 (status[b] == 1)，直接放入队列等待处理；否则放入 waiting，等后来拿到钥匙后再处理。

  3. 主循环：BFS 遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    while dq:
        i = dq.popleft()
        if opened[i]:
            continue
        # 打开盒子 i
        opened[i] = True
        ans += candies[i]
        # 拿到钥匙
        for k in keys[i]:
            if k not in have_key:
                have_key.add(k)
                if k in waiting:
                    waiting.remove(k)
                    dq.append(k)
        # 拿到内部的盒子
        for nb in containedBoxes[i]:
            if nb not in have_box:
                have_box.add(nb)
                if status[nb] == 1 or nb in have_key:
                    dq.append(nb)
                else:
                    waiting.add(nb)
    • 每次从队列中取出一个盒子 iii，若之前已打开过则跳过；否则标记 opened[i] = True，累加 ans += candies[i]。
    • 遍历 keys[i]：若新钥匙对应的盒子在 waiting 中，则表示现在能打开它，将其从 waiting 中移除并加入队列。
    • 遍历 containedBoxes[i]：若拿到的新盒子 nb 尚未“拥有”，加入 have_box；若该盒子本身已开或已有钥匙，则直接放入队列，否则加入 waiting。

    结束条件

    • 当 dq 为空时，无更多可直接打开的盒子；同时 waiting 中暂时无法打开的盒子若未来不能通过拿到钥匙打开，也无法再继续。不再有新钥匙或新盒子可激活，遍历结束。最终返回 ans。

时间复杂度

设：

  • n=n = 盒子总数；

  • m=∑i=0n−1(∣keys[i]∣+∣containedBoxes[i]∣)。m = \sum_{i=0}^{n-1} (|keys[i]| + |containedBoxes[i]|)。

  • 每个盒子在最坏情况下只会被加入队列并“打开”一次，复杂度约为 O(n)O(n)；

  • 对所有 keys[i] 和 containedBoxes[i] 共计 mm 个元素做遍历，复杂度为 O(m)O(m)；

  • 集合的插入、查找、删除平均为 O(1)O(1)。

因此，总时间复杂度为：O(n+m).O(n + m).

空间复杂度：

  • have_box、have_key、opened、waiting、队列 dq 均大小至多 O(n+m)O(n + m)，
  • 故空间复杂度也是：O(n+m).O(n + m).

代码分解

  1. 导入与类型定义

    1
    2
    from collections import deque
    from typing import List

  2. 类与函数签名

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution:
        def maxCandies(
            self,
            status: List[int],
            candies: List[int],
            keys: List[List[int]],
            containedBoxes: List[List[int]],
            initialBoxes: List[int]
        ) -> int:
            ...
    • status, candies, keys, containedBoxes 均长度为 nn；
    • initialBoxes 长度 ≤n\le n。

  3. 初始化状态数据结构

    1
    2
    3
    4
    5
    6
    7
    n = len(status)
    have_box = set(initialBoxes)
    have_key = set()
    opened = [False] * n
    waiting = set()
    dq = deque()
    ans = 0
    • n：盒子总数；
    • have_box：记录已拥有盒子；
    • have_key：记录已有钥匙；
    • opened[i]：标记盒子是否已打开取过糖果；
    • waiting：存储已拥有但因无钥匙无法打开的盒子；
    • dq：存储当前可直接打开的盒子，BFS 队列；
    • ans：累加糖果总数。

  4. 初始队列填充

    1
    2
    3
    4
    5
    for b in initialBoxes:
        if status[b] == 1:
            dq.append(b)
        else:
            waiting.add(b)
    • 若盒子已开（status[b] == 1），则直接放入 dq；否则放入 waiting 等待。

  5. 主循环：BFS 处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    while dq:
        i = dq.popleft()
        if opened[i]:
            continue
        # 打开盒子 i
        opened[i] = True
        ans += candies[i]
        
        # 获取钥匙
        for k in keys[i]:
            if k not in have_key:
                have_key.add(k)
                if k in waiting:
                    waiting.remove(k)
                    dq.append(k)
        # 获取内部盒子
        for nb in containedBoxes[i]:
            if nb not in have_box:
                have_box.add(nb)
                if status[nb] == 1 or nb in have_key:
                    dq.append(nb)
                else:
                    waiting.add(nb)

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from collections import deque
from typing import List

class Solution:
    def maxCandies(
        self,
        status: List[int],
        candies: List[int],
        keys: List[List[int]],
        containedBoxes: List[List[int]],
        initialBoxes: List[int]
    ) -> int:
        n = len(status)
        
        # 1. 初始化数据结构
        have_box = set(initialBoxes)     # 当前已拥有的盒子
        have_key = set()                 # 当前已拥有的钥匙
        opened = [False] * n             # 标记是否已打开并取过糖果
        waiting = set()                  # 已拥有但因无钥匙暂时无法打开的盒子
        dq = deque()                     # BFS 队列：可直接打开的盒子
        ans = 0                          # 累加糖果数量
        
        # 2. 初始队列填充
        for b in initialBoxes:
            if status[b] == 1:
                dq.append(b)
            else:
                waiting.add(b)
        
        # 3. BFS 主循环
        while dq:
            i = dq.popleft()
            # 如果已打开过，则跳过
            if opened[i]:
                continue
            
            # 打开盒子 i
            opened[i] = True
            ans += candies[i]
            
            # 3.1 拿到钥匙，尝试打开 waiting 中对应的盒子
            for k in keys[i]:
                if k not in have_key:
                    have_key.add(k)
                    if k in waiting:
                        waiting.remove(k)
                        dq.append(k)
            
            # 3.2 拿到新盒子，判断是否可直接打开或放入 waiting
            for nb in containedBoxes[i]:
                if nb not in have_box:
                    have_box.add(nb)
                    if status[nb] == 1 or nb in have_key:
                        dq.append(nb)
                    else:
                        waiting.add(nb)
        
        # 4. 返回最大糖果数
        return ans