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

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数组 广度优先搜索 图

题目描述

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

image-20260929080458787

image-20260929080458937

image-20260929080459066

题意分析

初始持有一些盒子，每个盒子里有糖果、其他盒子的钥匙以及内含盒子。只有已经拿到某个盒子，并且它原本开启或对应钥匙已经得到，才能打开它并领取内容。

钥匙与盒子是不同资源：有钥匙不等于持有对应盒子，拿到锁着的盒子也不代表马上能打开。开盒后可以继续获得资源，求最终能够拿到的全部糖果总数，同一盒子的糖果只能计算一次。

解法：BFS + 状态驱动

核心思路

[!blue]

分别维护 hasBox 表示已经持有，hasKey 表示已经拿到钥匙，queued 表示是否安排过处理。可以入队的条件是“持有盒子、已具备打开条件、尚未安排”，打开条件为原状态开启或者已经有钥匙。

先标记全部初始盒子，再将其中原本开启的盒子入队。每弹出一个盒子，它已经满足条件，可以领取糖果并发布两类新信息：拿到了哪些钥匙、拿到了哪些内含盒子。

获取钥匙时先记录 hasKey[k]，若盒子 k 已持有且尚未安排，就能唤醒它；此时钥匙本身已经保证可打开。获取盒子时先记录 hasBox[b]，再检查它原本是否开启，或此前是否已经取得钥匙。两种资源可能按任意顺序到达，所以两类事件都必须重新检查。

queued 在入队时设为真，之后不再清除，它同时覆盖正在排队和已经结算的盒子。不同事件反复提到同一盒子时，也只会处理一次。暂时打不开的盒子仍然保留在 hasBox 中，不会因为第一次失败就被丢弃。

获得资源只会增加可打开的盒子，开盒也不会损失已有能力，所有糖果都为正，因此任何当前可开盒子都值得处理，不需要在顺序之间做选择。队列耗尽时，所有已满足条件的盒子都已结算，也没有新的资源来源，留下的锁盒或未持有盒子无法再贡献糖果。

解题步骤

  1. 初始化三组状态，登记全部初始持有盒子。
  2. 将原本开启且尚未安排的初始盒子入队，立即标记 queued。
  3. 弹出盒子并累加糖果，逐个登记它提供的钥匙，尝试安排已经持有的对应盒子。
  4. 逐个登记内含盒子，原本开启或已经有钥匙时，尝试首次入队。
  5. 重复处理，直到没有待处理盒子，返回累计糖果数。初始没有可开盒子时自然返回零。

代码实现

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[] 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();

            total += candies[box];

            for (int k : keys[box]) {
                // 先记录钥匙，再尝试唤醒已经持有的对应锁盒。
                hasKey[k] = true;

                if (hasBox[k] && !queued[k]) {
                    // 入队时就标记安排过，避免重复结算。
                    queued[k] = true;
                    queue.offer(k);
                }
            }

            // 新盒子也可能早已有钥匙，另一种到达顺序同样要检查。
            for (int b : containedBoxes[box]) {
                hasBox[b] = true;

                if (!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)
    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]
        total += candies[box]

        for _, k := range keys[box] {
            // 先记录钥匙，再尝试唤醒已经持有的对应锁盒。
            hasKey[k] = true
            if hasBox[k] && !queued[k] {
                // 入队时就标记安排过，避免重复结算。
                queued[k] = true
                queue = append(queue, k)
            }
        }

        // 新盒子也可能早已有钥匙，另一种到达顺序同样要检查。
        for _, b := range containedBoxes[box] {
            hasBox[b] = true
            if !queued[b] && (status[b] == 1 || hasKey[b]) {
                queued[b] = true
                queue = append(queue, b)
            }
        }
    }

    return total
}

复杂度分析

  • 时间复杂度：$O(n+K+B)$，n 为盒子总数，K、B 分别为全部钥匙列表与内含盒子列表长度。每个盒子最多入队一次，实际只扫描已打开盒子的列表。
  • 空间复杂度：$O(n)$，三组状态和待处理队列均为线性大小，输入列表不复制。

关键点总结

[!green]

  • 持有和可打开是两个独立条件，只有同时满足才能领取内容。
  • 新钥匙和新盒子分别触发检查，兼容任意资源到达顺序。
  • 入队立即标记，已经安排过的盒子永久去重，糖果不会重复计入。
  • 资源单调增加，没有开盒代价，处理所有可达且可开的盒子就是最大收益。

易错点总结

[!yellow]

  • 只要取得钥匙就计算对应糖果，可能根本还未拿到那只盒子。
  • 发现锁盒没有钥匙就丢弃，后来拿到钥匙时无法重新启用它。
  • 只在获得盒子时检查，或者只在获得钥匙时检查，会漏掉另一种先后顺序。
  • 到出队时才标记或出队后清除标记，多个事件可能将同一盒子重复入队、重复计糖。
  • 把原本已开启的盒子也要求必须有钥匙，错误增加开盒条件。
  • 认为题名中的最大值需要枚举开盒顺序，忽略了开盒不会损失资源，顺序不影响最终可获得集合。

相似题目

题目 难度 关联与区别
841. 钥匙和房间 中等 拿到钥匙都可解锁后续对象，但本题必须同时持有盒子且已能打开，不能只凭钥匙直接取糖果。
2115. 从给定原材料中找到所有可以做出的菜 中等 同样在先决条件满足时才把对象加入可处理队列，并传播新获得的资源。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/34578029
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！