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

约 5 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 LeetCode 75
标签
哈希表 设计 堆（优先队列） 有序集合

题目描述

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

image-20260928234514457

image-20260928234514459

题意分析

集合一开始包含所有正整数。popSmallest() 取出并删除当前最小元素，addBack(num) 在该正整数不在集合中时将它放回。

集合不能包含重复元素，重复加回没有效果；从未被取出的数本来就在集合中，也无需重新添加。虽然范围无限，但操作只会改变有限数量的已取出值，不需要真的存下全部正整数。

解法：连续尾部边界与加回堆

核心思路

[!blue]

用边界 next 表示从未被取出的连续后缀 [next, +∞)，其中全部数都还在集合中。比 next 小的数已经至少被取出过，它们只有在后来被加回、并且还未再次弹出时，才仍属于集合。

把这部分加回的较小值放入最小堆 back。整个集合就表示为“堆中有限个离散值”加“边界开始的无限连续后缀”。堆中所有值都小于 next，所以堆非空时全局最小值一定是堆顶；堆空时才返回 next，并将后缀边界加一。

addBack 只需处理 num < next 的值，较大值原本还在连续后缀中。为了防止同一个值重复入堆，另外用哈希集合 inBack 记录堆中的成员；不在其中才同时加入集合与堆。弹出堆顶时也从集合删除，让这个数将来可以再次被加回。

边界只在第一次取出连续后缀的最小值时前进，不会因弹出加回值而移动。这样每次操作都维持两个部分互不重叠、合起来恰好是当前无限集合的状态。

解题步骤

  1. 初始化 next = 1，加回堆与判重集合都为空。
  2. 弹出最小时，堆非空就取堆顶，并删除其判重标记。
  3. 堆为空则返回当前 next，再将边界加一。
  4. 加回时，只有值小于 next 且尚不在堆中，才同时加入判重集合与最小堆。
  5. 其他加回操作不改变状态。

代码实现

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);
        }
    }
}

import (
    "container/heap"
)

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)$；设操作期间加回堆的最大规模为 q，实际入堆、出堆为 $O(\log(q+1))$，从连续后缀取数或忽略重复添加为期望 $O(1)$。
  • 空间复杂度：$O(q+1)$，堆与判重集合只保存有限的加回元素，连续无限后缀只用一个边界表示。这里用最大规模计入容器可能保留的容量。

关键点总结

[!green]

  • 未取过的连续无限部分不逐个存储，边界就能完整表示。
  • 加回堆中值都小于边界，决定弹出时必须优先看堆。
  • 堆负责最小值，集合负责去重，两者成员始终同步。
  • 同一个值可以多次经历取出和加回，但同时最多存在一份。

易错点总结

[!yellow]

  • 将 num >= next 的值也加入堆，它本来就在无限后缀，会制造重复元素。
  • 不对加回值去重，连续多次添加后同一个数可能被重复弹出。
  • 弹出堆顶后不删除判重标记，之后合法的再次加回会被错误拒绝。
  • 弹出加回值时也推进 next，跳过了仍然存在的后缀首项。
  • 试图预先创建整个无限集合，或者随意截取固定上限，偏离了有限操作状态的表示方式。

相似题目

题目 难度 关联与区别
1845. 座位预约管理系统 中等 同样分配最小可用编号并支持归还，原题编号范围有限，本题用边界表示无限尾部。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/55293584
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！