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

Categories:

题目描述
思路分析
1. 解法一：BFS + 状态驱动（推荐）
相似题目

题目描述

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

思路分析

解法一：BFS + 状态驱动（推荐）

核心思路：

用 hasBox 记录已获得的盒子，用 hasKey 记录已拿到的钥匙。

只要盒子可打开（状态为开或已有钥匙），就入队并处理。

处理盒子时收集糖果、钥匙、包含的盒子，并推动新可开盒子入队。

复杂度分析：

时间复杂度：O(n + m)，其中 n 为盒子数，m 为包含关系总数。

空间复杂度：O(n + m)。

import java.util.ArrayDeque;
import java.util.Queue;

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];

        Queue<Integer> queue = new ArrayDeque<>();
        for (int b : initialBoxes) {
            hasBox[b] = true;
        }
        for (int b : initialBoxes) {
            if (status[b] == 1) {
                queue.offer(b);
            }
        }

        int total = 0;
        while (!queue.isEmpty()) {
            int box = queue.poll();
            if (opened[box]) {
                continue;
            }
            if (status[box] == 0 && !hasKey[box]) {
                continue;
            }
            opened[box] = true;
            total += candies[box];

            // 获取钥匙
            for (int k : keys[box]) {
                if (!hasKey[k]) {
                    hasKey[k] = true;
                    if (hasBox[k] && !opened[k]) {
                        queue.offer(k);
                    }
                }
            }

            // 获取盒子
            for (int b : containedBoxes[box]) {
                if (!hasBox[b]) {
                    hasBox[b] = true;
                }
                if (!opened[b] && (status[b] == 1 || hasKey[b])) {
                    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)

    queue := make([]int, 0)
    for _, b := range initialBoxes {
        hasBox[b] = true
    }
    for _, b := range initialBoxes {
        if status[b] == 1 {
            queue = append(queue, b)
        }
    }

    total := 0
    for head := 0; head < len(queue); head++ {
        box := queue[head]
        if opened[box] {
            continue
        }
        if status[box] == 0 && !hasKey[box] {
            continue
        }
        opened[box] = true
        total += candies[box]

        // 获取钥匙
        for _, k := range keys[box] {
            if !hasKey[k] {
                hasKey[k] = true
                if hasBox[k] && !opened[k] {
                    queue = append(queue, k)
                }
            }
        }

        // 获取盒子
        for _, b := range containedBoxes[box] {
            if !hasBox[b] {
                hasBox[b] = true
            }
            if !opened[b] && (status[b] == 1 || hasKey[b]) {
                queue = append(queue, b)
            }
        }
    }

    return total
}

相似题目

题目	难度	考察点
210. 课程表 II	中等	图遍历
200. 岛屿数量	中等	BFS/DFS
841. 钥匙和房间	中等	BFS
994. 腐烂的橘子	中等	BFS
207. 课程表	中等	图遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/34578029