2336. Smallest Number in Infinite Set

📘 題目敘述

你有一個包含所有正整數的集合 InfiniteSet，也就是 {1, 2, 3, ...}。

請你實作 SmallestInfiniteSet 類別，支援以下操作：

SmallestInfiniteSet()：初始化物件，使其包含所有正整數
int popSmallest()：移除並回傳集合中目前最小的整數
void addBack(int num)：如果 num 不在集合中，則把它加回集合中

條件限制

1 <= num <= 1000
最多呼叫 popSmallest 與 addBack 總共 1000 次

🧠 解題思路

這題的關鍵是：集合一開始是無限的 {1,2,3,...}，所以我不可能真的把所有數存起來。

我用兩個結構去描述目前集合的狀態：

first：代表「目前還沒被 pop 掉的最小自然數指標」

也就是說，所有 >= first 的數字，預設都還在集合裡（因為無限）
而 1..first-1 都已經被 pop 過了（除非有被 addBack）

q（min-heap）：用來存那些「被 pop 過，但後來被 addBack 回來」的數字

這些數可能比 first 小，所以 popSmallest() 時要優先處理它們
我用 greater<int> 讓 q.top() 永遠是目前 heap 裡最小的那個

popSmallest() 時的邏輯是：

如果 heap 裡有東西，而且 q.top() < first

代表集合裡目前最小的數字其實是這個被 addBack 的數
直接把它 pop 出來回傳

否則

代表 heap 沒有更小的數可以用
那集合最小值就是 first
回傳 first，並把 first++，表示它被取走了

addBack(num) 時：

只有當 num < first 時才可能是「之前被 pop 掉的數」
所以只在 num < first 的時候把它丟進 heap，表示它被加回來了

所有變數

first：目前尚未被取走的最小自然數指標（預設集合從 first 開始連續存在）
q：min-heap，存所有被 addBack 回來、且小於 first 的數字

🪜 主要流程步驟

1. 初始化 first = 1

一開始集合是 {1,2,3,...}，所以最小值就是 1，用 first = 1 表示。

2. popSmallest：先看 heap 有沒有比 first 更小的數

如果 q 不空，且 q.top() < first：

代表目前集合裡存在一個更小的數（它是之前被 pop 過，後來 addBack 回來的），所以我取出並回傳 q.top()。

3. popSmallest：否則回傳 first，並把 first 往後推一格

如果 heap 沒有可用的更小數，代表集合中最小的就是 first。

我回傳 first，再 first++，表示這個數已經被移除，下一個候選會變成更大的數。

4. addBack：只處理 num < first 的情況

如果 num >= first，代表它本來就還在集合裡（因為 first 之後都是連續存在的），不需要做事。

如果 num < first，代表它可能是之前被 pop 掉的數，我就把它丟進 heap，讓之後能被 popSmallest() 拿回來。

⏱️ 複雜度

popSmallest()：O(log m)，m 是 heap 裡的元素數量（push/pop 都是 log）
addBack()：O(log m)（需要 push 時）
空間複雜度：O(m)，heap 只存被加回來的數字

💻 程式碼實作

class SmallestInfiniteSet {
public:
    int first;
    priority_queue<int, vector<int>, greater<int>> q;
    SmallestInfiniteSet() {
        first = 1;
    }

    int popSmallest() {
        if (!q.empty() && q.top() < first) {
            int k = q.top();
            q.pop();
            return k;
        } else {
            first++;
            return first - 1;
        }
    }

    void addBack(int num) {
        if (num < first) {
            q.push(num);
        }
    }
};

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */

🔗 題目連結

https://leetcode.com/problems/smallest-number-in-infinite-set/