系統設計: 動態取出數據流的最小值 Leetcode #2336_Leetcode 精選75題解析

Andy Holmes on Unsplash

題目敘述

題目的情境是設計並且實現一個包含所有正整數的數據流，以set集合的方式存在。

數據流 = {1, 2, 3, 4, ..., ∞}

要求我們去實現定義好的function介面:

SmallestInfiniteSet()建構子，初始化這個包含所有正整數的數據流。

int popSmallest()，取出並且回傳數據流目前的最小值。

void addBack(int num)，假如num目前不在數據流裡面，則插入一個數字num到數據流裡面。

題目的原文敘述

測試範例

Example 1:

Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1);    // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
                                   // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

約束條件

Constraints:

• 1 <= num <= 1000

插入的新數字num數值會介於1~1000之間。

• At most 1000 calls will be made in total to popSmallest and addBack.

動態測試時，最多會有1000次function call。

演算法

從題目的需求來尋找底層適合的資料結構data structure。

要維護一個動態的數據流，而且又要支持取出最小值的操作。

聯想到優先權佇列 或者說 最小堆 minheap，python已經內建支援min heap最小推，實作在heapq這個 library裡面。

插入新元素時，又要維持元素唯一沒有重複的性質，聯想到hash set 集合，在python也已經內建支援set()。