LeetCode 2336. 无限集中的最小数字

2026-07-14 HGNULB 约 11 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 2336. 无限集中的最小数字

题意分析

要设计一个类，它一开始装着全体正整数 [1, 2, 3, ...]，支持两个操作：popSmallest() 取走并返回当前集合里最小的数；addBack(num) 把 num 放回集合，但如果 num 本来就还在集合里，这次调用什么都不做。

「无限」两个字是唯一的设计难点：集合的元素个数没有上界，不可能真的建出来。但换个角度看，被动过手脚的只是很小一部分 —— 任何时刻，集合都可以描述成「一段被挖掉若干个洞的正整数序列」，而洞的总数受操作次数限制。这提示我们：只需要显式维护被改动的部分，未被触及的那条无限尾巴用一个数字就能代表。

addBack 的语义要抠仔细。它是「放回」而不是「插入」：只有当 num 曾经被 popSmallest 取走、此刻确实不在集合里时才生效。官方样例开头就是陷阱 —— 一上来 addBack(2)，此时 2 还好端端地在集合里，所以这次调用必须完全无效，紧接着的 popSmallest() 依然要返回 1。第二个陷阱藏在样例之外：对同一个数连续 addBack 两次，第二次也是无效的，因为第一次之后它已经回到集合里了，集合不能装重复元素。

约束是 1 <= num <= 1000，且 popSmallest 与 addBack 合计最多调用 1000 次。这两条一起说明：被挖出的洞最多 1000 个，被加回的数也最多 1000 个，规模极小；同时 num 有上界意味着不会有人把一个天文数字加回来。边界情形有两个：从未调用过 addBack 时，连续 popSmallest 就是依次返回 1, 2, 3, ...；以及所有加回的数都被重新取完之后，要能无缝接回那条无限尾巴继续往下数。

解法：边界指针 + 小根堆维护加回的数

核心思路

朴素想法是开一个足够大的布尔数组（比如 1001 个位置）标记在与不在，popSmallest 从头扫第一个为真的位置。这在本题的约束下其实能过，但它有两处不体面：一是每次弹出最坏要扫 1000 格，操作复杂度是 $O(U)$ 而不是对数级；二是它彻底依赖 num <= 1000 这条约束，一旦上界放宽到 $10^9$，方案立刻报废。面试官问的往往正是「如果 num 可以很大呢」。

真正的关键观察是：集合永远可以拆成互不重叠的两部分 —— 一部分是「从某个边界 next 开始、往后连续到无穷的所有整数」，另一部分是「小于 next 且被加回来的那些零散的数」。为什么这个划分总是成立？因为 popSmallest 只会从最小处取走，取走的一定是一段前缀里的数；而 addBack 只能把已经取走的数放回来，那些数必然小于 next。于是不变量可以写死：next 是从未被弹出过的最小整数，[next, +∞) 全部在集合中；小于 next 的数只有落在容器 back 里的才在集合中。

有了这条不变量，两个操作都变得直白。popSmallest 要在两部分里取较小者：back 里的数按定义全都小于 next，所以只要 back 非空，答案就一定来自 back，不需要真的比大小；back 为空时答案就是 next，取走后 next 自增一格，无限尾巴的起点顺势右移。addBack(num) 则只在 num < next（说明它确实被弹出过）且它还不在 back 里时才把它放进去，这两个条件正是题目「已存在则不操作」的完整翻译。

back 需要支持「插入」和「取最小」，小根堆是最自然的选择，两个操作都是 $O(\log back )$。但堆本身不去重，contains 也要 $O( back )$，所以额外配一个哈希集合专门做存在性判断：弹出时同步移除，加回时先查后插。堆与集合的内容始终保持一致，这是第二条必须守住的不变量。

顺带一提，因为本题 num <= 1000 且总调用不超过 1000 次，直接用「有序集合」（如 TreeSet）一个容器同时解决排序与去重也完全可行，代码更短；这里选堆加哈希集合，是因为它对 num 的上界没有任何依赖，泛化性更好，也更贴近面试官想听的答案。

解题步骤

定义三个成员：整数 next 初始为 1，小根堆 back，哈希集合 inBack。为什么：next 代表那条无限尾巴的起点，back 负责在零散的数里取最小，inBack 负责 $O(1)$ 判重 —— 堆自身查存在性要线性时间，必须分工。

popSmallest() 先看 back 是否为空。为什么：back 里的数按不变量全都小于 next，只要它非空，全局最小值一定在里面，连比较都省了。

若 back 非空，弹出堆顶 num，同时从 inBack 里删掉 num，返回 num。为什么：堆和集合必须同步，否则这个数以后再被 addBack 时会被误判成「已在集合里」而永久丢失。

若 back 为空，返回 next 并让 next 自增。为什么：此时集合就是 [next, +∞)，最小值即 next；自增等于把无限尾巴的起点右移一格，不变量继续成立。

addBack(num) 先判断 num < next。为什么：num >= next 说明它从未被弹出、此刻仍在集合中，按题意必须什么都不做 —— 这正是官方样例第一步 addBack(2) 要被忽略的原因。

再判断 num 是否已在 inBack 中，不在才同时插入 inBack 和 back。为什么：集合不装重复元素，连续两次 addBack(1) 的第二次必须无效，否则 1 会被弹出两遍。

以官方样例走一遍：调用序列是 addBack(2)、三次 popSmallest、addBack(1)、三次 popSmallest，期望输出 1, 2, 3, 1, 4, 5。

初始 next = 1，back 与 inBack 都为空。addBack(2)：2 < 1 不成立，直接忽略 —— 这一步做对了，后面才可能对。第一次 popSmallest：back 空，返回 1，next 变 2。第二次：back 仍空，返回 2，next 变 3。第三次：返回 3，next 变 4。此刻不变量是「[4, +∞) 在集合中，1、2、3 已被取走」。

addBack(1)：1 < 4 成立，且 inBack 里没有 1，于是 inBack = {1}、back = {1}。第四次 popSmallest：back 非空，弹出 1 并从 inBack 移除，返回 1。第五次：back 又空了，返回 next = 4，next 变 5。第六次：返回 5，next 变 6。输出序列 1, 2, 3, 1, 4, 5，与期望完全一致。

重复加回的边界：新建对象后连续两次 popSmallest 得到 1, 2（next = 3），然后 addBack(1)、addBack(1)、addBack(2)。第一次 addBack(1) 生效，第二次因为 inBack 已有 1 被忽略，addBack(2) 生效。此时 back = {1, 2}。接下来三次 popSmallest 依次返回 1、2、3 —— 前两个来自堆、第三个来自尾巴，无缝衔接。若漏掉判重，第二次会返回 1 而不是 2。

代码实现

class SmallestInfiniteSet {
    // 不变量：[next, +∞) 全在集合中；小于 next 的数只有在 back 里的才在集合中。
    private int next = 1;
    private PriorityQueue<Integer> back = new PriorityQueue<>();
    // 堆查存在性是 O(n)，用哈希集合专门负责判重，两者内容始终同步。
    private Set<Integer> inBack = new HashSet<>();

    public SmallestInfiniteSet() {
    }

    public int popSmallest() {
        if (!back.isEmpty()) {
            // back 里的数一律小于 next，非空时全局最小值必在其中。
            int num = back.poll();
            inBack.remove(num);
            return num;
        }
        // 集合退化成 [next, +∞)，取走后边界右移一格。
        return next++;
    }

    public void addBack(int num) {
        // num >= next 说明它从未被弹出，仍在集合中，按题意忽略。
        if (num < next && inBack.add(num)) {
            back.offer(num);
        }
    }
}

type SmallestInfiniteSet struct {
    // 不变量：[next, +∞) 全在集合中；小于 next 的数只有在 back 里的才在集合中。
    next   int
    back   *IntHeap
    inBack map[int]bool
}

func Constructor() SmallestInfiniteSet {
    return SmallestInfiniteSet{next: 1, back: &IntHeap{}, inBack: map[int]bool{}}
}

func (s *SmallestInfiniteSet) PopSmallest() int {
    if s.back.Len() > 0 {
        // back 里的数一律小于 next，非空时全局最小值必在其中。
        num := heap.Pop(s.back).(int)
        delete(s.inBack, num)
        return num
    }
    // 集合退化成 [next, +∞)，取走后边界右移一格。
    s.next++
    return s.next - 1
}

func (s *SmallestInfiniteSet) AddBack(num int) {
    // num >= next 说明它从未被弹出，仍在集合中，按题意忽略。
    if num < s.next && !s.inBack[num] {
        s.inBack[num] = true
        heap.Push(s.back, num)
    }
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

复杂度分析

时间复杂度：构造是 $O(1)$；popSmallest 与 addBack 均为 $O(\log q)$，其中 $q$ 是堆中元素个数。堆里只可能装被弹出过又被加回的数，所以 $q$ 不超过总调用次数，本题即 $q \le 1000$，log 部分不到 10 次比较；哈希集合的增删查是均摊 $O(1)$，不改变量级。

空间复杂度：$O(q)$，堆和哈希集合各存一份被加回的数，两者规模同阶且受总调用次数限制；那条无限尾巴只用 next 一个整数表示，不占任何与值域相关的空间。

关键点总结

无限结构要用「规则 + 例外」来表示，而不是枚举。[next, +∞) 用一个整数代表规则，堆和集合记录有限的例外，两者拼起来就是完整的集合。凡是遇到「无限集合」「无限流」，先想能不能这样切一刀。

划分要做到互不重叠，比较才可以省掉。因为「加回的数一律小于 next」是硬性不变量，popSmallest 才敢在 back 非空时直接返回堆顶而不与 next 比较。如果两部分可能重叠，这一步就必须比大小，代码和推理都会变复杂 —— 好的划分能让后续逻辑自动简化。

堆负责排序，哈希集合负责判重，各司其职。优先队列的 contains 是线性时间，用它来判重会把单次操作拖成 $O(q)$；多花一份 $O(q)$ 空间换 $O(1)$ 判重是标准做法，代价是必须保证两个容器同步增删。

「已存在则不操作」是两个条件的合取，缺一不可：num 必须曾被弹出（num < next），且此刻不在待加回的容器里。只写其中一个，官方样例或重复加回的用例就会挂。

面试视角：这题真正被考的是「你会不会真的去构造那个无限集合」。开一个 1001 长度的布尔数组能过，但一定会被追问「如果 num 的上界是 $10^9$ 呢」，这时边界指针加堆的方案不改一行就能成立，而数组方案彻底失效 —— 主动说明这一点，比先写数组再被问倒好得多。另一个高频追问是「为什么需要哈希集合，堆不够吗」，答案是堆无法 $O(1)$ 判重，而重复元素会直接违反集合语义。

易错点总结

addBack 不检查 num < next：新建对象后 addBack(2)，接着连续三次 popSmallest → 输出 2, 1, 2，期望是 1, 2, 3。2 被凭空塞进堆里抢先弹出，之后又从尾巴上弹出一次，同一个数返回了两遍。官方样例第一步就是这个陷阱，漏掉它连样例都过不了。

addBack 不做重复判断：连续两次 popSmallest 得到 1, 2 后，addBack(1) 调两次，再连续三次 popSmallest → 输出 1, 1, 3，期望是 1, 3, 4。集合被塞进了重复元素，1 弹了两遍还把 2 挤没了。官方样例里没有连续加回同一个数的场景，这条只能靠自己补用例。

popSmallest 从堆里弹出后忘了同步删 inBack：这个数以后再被 addBack 时会因为「集合里已有」被忽略，从此永久丢失。表现是某个数被弹出两次之后就再也拿不回来，且不会报错 —— 属于最难查的那类静默不一致，两个容器必须成对增删。

自增写成 return ++next：新建对象后连续三次 popSmallest → 输出 2, 3, 4，期望是 1, 2, 3。前缀自增先加后返回，整条序列平移一位，第一个数就错。改成后缀自增，或者先存再加。

popSmallest 时拿堆顶和 next 比大小再挑一个：逻辑上不算错，但会掩盖不变量被破坏的事实 —— 若某处误把大于等于 next 的数放进了堆，这个写法会「优雅地」绕过去继续跑，把 bug 藏到很后面才爆发。不比较、直接信任堆，反而能让上游的错误立刻现形。

用 PriorityQueue.contains 代替哈希集合判重：结果正确，但单次 addBack 退化成 $O(q)$，总复杂度变成平方级。本题 1000 次调用还扛得住，换成 $10^5$ 次调用就会超时，属于「能过但站不住」的写法。

用大根堆或忘记指定比较器：back 会弹出加回集合里最大的那个数。连续弹出 1, 2 后 addBack(1)、addBack(2)，再弹出 → 得到 2, 1，期望是 1, 2。这个错误在只加回一个数时完全测不出来。

只用一个哈希集合、不用堆，靠遍历找最小：正确性没问题，但每次 popSmallest 都要扫一遍集合，操作退化成线性；更麻烦的是集合里元素的顺序不确定，稍不留神就写成「返回任意一个」而不是「返回最小的」。

开固定长度数组标记在与不在：本题因为 num <= 1000 能过，但每次弹出最坏要扫 1000 格；一旦 num 的上界放宽，方案直接失效。这是典型的「依赖具体约束而非题目结构」的解法，面试中容易被一句追问推翻。

相似题目

题目	难度	考察点
703. 数据流中的第 K 大元素	简单	同样是堆撑起来的设计题，但堆的大小固定为 `k`、只维护前 `k` 大，没有「无限尾巴」这一层抽象
1046. 最后一块石头的重量	简单	纯粹的堆模拟，反复取两个最大值再放回差值，可用来单独熟悉优先队列的增删语义
380. O(1) 时间插入、删除和获取随机元素	中等	同样靠「两种容器分工」达成各操作的目标复杂度，只是取的是随机元素而非最小元素
155. 最小栈	中等	也是「常规容器 + 辅助结构」维护最小值，但受栈的后进先出约束，用单调栈而非堆
933. 最近的请求次数	简单	同为流式设计题，靠队列淘汰过期数据来避免存下全部历史，与本题「只存例外」的思路呼应