LeetCode 1298. 你能从盒子里获得的最大糖果数
目录
题目描述
题意分析
有 n 个盒子，每个盒子有开关状态、装着若干糖果、可能装着若干钥匙、也可能装着若干别的盒子。初始手上有一批盒子，问最终能拿到多少糖果。
打开一个盒子需要同时满足两个条件：手上有这个盒子，并且它是开着的或者你有它的钥匙。这是两个正交的条件，缺一不可——有钥匙但盒子还没拿到，打不开；拿到了盒子但它锁着又没钥匙，也打不开。
这两个条件的获得顺序完全不确定：可能先拿到钥匙后拿到盒子，也可能反过来。这意味着不能用一次固定顺序的扫描解决，必须让「新获得钥匙」和「新获得盒子」这两类事件都能触发对某个盒子的重新检查。
打开一个盒子会同时产出三样东西：糖果（直接累加）、钥匙（可能解锁手上已有的盒子）、盒子（可能立刻可开，也可能要等钥匙）。所以打开动作是会产生连锁反应的，整个过程像一个不断扩散的可达集合。
规模：盒子数最多 1000，各个列表的总长度也在千级，$O(n + m)$ 的一趟扩散完全够用。答案只要总糖果数，不关心打开顺序或步数。
边界：初始盒子全是锁着的且没钥匙（答案 0）、钥匙指向自己、盒子互相嵌套形成环、拿到钥匙时对应盒子还没到手、同一个盒子被多次「获得」。
解法：BFS + 状态驱动
核心思路
盒子
i可处理，当且仅当同时满足：已经持有它，并且它本来打开或已经拿到钥匙。两个条件可能以任意顺序到达，因此用事件驱动的 BFS：拿到新盒子、拿到新钥匙时，都检查对应盒子是否刚变得可处理。分别维护四个状态：
hasBox表示已持有，hasKey表示已有钥匙，queued表示已经安排处理，opened表示已经打开并结算。只有“已持有且可打开”的盒子才入队，并在入队时设置queued，从而保证每个盒子至多入队一次。不变量：队列里的每个盒子都已持有、可打开且此前未处理；
opened[i]为真时，盒子i的糖果、钥匙和内含盒子恰好处理过一次。任何尚未打开但条件已经齐全的盒子，要么正在队列中，要么会在最后一个条件到达的事件中被加入队列。正确性：初始可开的盒子全部入队。打开盒子后，只有“获得钥匙”和“获得盒子”会改变其他盒子的可处理性，代码在这两个事件点都重新检查，因此不会漏掉任何最终可开的盒子。
queued防止重复安排，opened防止重复结算，所以每颗可获得的糖果恰好累加一次。
解题步骤
- 先标记全部
initialBoxes为已持有，再把其中本来打开的盒子去重入队。- 每次出队后标记已打开，累加糖果。
- 处理其中的钥匙：记录钥匙；若对应盒子已持有且尚未排队，则入队。
- 处理其中的盒子：记录持有；若它本来打开或已有钥匙，且尚未排队，则入队。
- 队列耗尽后返回糖果总数。
样例
status=[1,0,1,0]、candies=[7,5,4,100]中，先开 0 得到盒子 1、2，再开 2 得到钥匙 1，随后开 1；盒子 3 始终没有钥匙，答案为7+4+5=16。反例体现条件到达顺序：若先持有锁着的盒子 1、后获得钥匙 1，只在“获得盒子”时检查会漏开；若先获得钥匙、后持有盒子，只在“获得钥匙”时检查也会漏开。
代码实现
import java.util.ArrayDeque;
class Solution {
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
int n = status.length;
boolean[] hasBox = new boolean[n];
boolean[] hasKey = new boolean[n];
boolean[] opened = new boolean[n];
boolean[] queued = new boolean[n];
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int b : initialBoxes) {
hasBox[b] = true;
}
for (int b : initialBoxes) {
if (status[b] == 1 && !queued[b]) {
queued[b] = true;
queue.offer(b);
}
}
int total = 0;
while (!queue.isEmpty()) {
int box = queue.poll();
opened[box] = true;
total += candies[box];
for (int k : keys[box]) {
hasKey[k] = true;
if (hasBox[k] && !opened[k] && !queued[k]) {
queued[k] = true;
queue.offer(k);
}
}
for (int b : containedBoxes[box]) {
hasBox[b] = true;
if (!opened[b] && !queued[b] && (status[b] == 1 || hasKey[b])) {
queued[b] = true;
queue.offer(b);
}
}
}
return total;
}
}
func maxCandies(status []int, candies []int, keys [][]int, containedBoxes [][]int, initialBoxes []int) int {
n := len(status)
hasBox := make([]bool, n)
hasKey := make([]bool, n)
opened := make([]bool, n)
queued := make([]bool, n)
queue := make([]int, 0)
for _, b := range initialBoxes {
hasBox[b] = true
}
for _, b := range initialBoxes {
if status[b] == 1 && !queued[b] {
queued[b] = true
queue = append(queue, b)
}
}
total := 0
for head := 0; head < len(queue); head++ {
box := queue[head]
opened[box] = true
total += candies[box]
for _, k := range keys[box] {
hasKey[k] = true
if hasBox[k] && !opened[k] && !queued[k] {
queued[k] = true
queue = append(queue, k)
}
}
for _, b := range containedBoxes[box] {
hasBox[b] = true
if !opened[b] && !queued[b] && (status[b] == 1 || hasKey[b]) {
queued[b] = true
queue = append(queue, b)
}
}
}
return total
}
复杂度分析
- 时间复杂度：$O(n+K+B)$，其中
K、B分别是所有钥匙列表和内含盒子列表的总长度。每个盒子最多入队、打开一次，每个已打开盒子的列表只扫描一次。- 空间复杂度：$O(n)$，用于状态数组和队列。
关键点总结
- 可打开性由“持有盒子”和“盒子已解锁”两个独立、单调的条件共同决定。
- 两种条件的到达顺序不确定，所以两个事件点都必须尝试调度。
- 只把条件已齐全的盒子入队；
queued在入队时去重，opened记录已结算状态。- 暂时打不开的盒子不能丢弃，持有状态要保留到以后获得钥匙。
- 队列只是待处理集合，本题不依赖 BFS 层数。
易错点总结
- 只在获得盒子时检查：先有锁盒、后有钥匙的样例会漏掉盒子 1，结果从 16 变成 11。
- 只在获得钥匙时检查：先有钥匙、后拿到盒子时同样漏开。
- 有钥匙就直接打开而不检查
hasBox：会打开尚未持有的盒子。- 把锁盒也入队并立即标记为“访问过”：后来获得钥匙时无法重新调度。
- 没有
queued/opened去重：同一盒子从多条包含关系到达时会重复累加糖果。- 拿到暂不可开的盒子却不记录
hasBox：后续钥匙事件无法补齐条件。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 841. 钥匙和房间 | 中等 | 只有钥匙一个条件，拿到即可进入，不存在双条件的顺序问题 |
| 207. 课程表 | 中等 | 解锁条件是入度归零，需要用计数器而非布尔标记来判断可执行 |
| 994. 腐烂的橘子 | 中等 | 多源扩散且必须按层计时，队列在那里承担真正的顺序语义 |
| 133. 克隆图 | 中等 | 遍历的同时构造副本，访问表要存映射关系而不只是布尔标记 |