給定連續的整數流和兩個堆棧。我想實現在O（1）複雜度下運行的extractMin操作。此操作從記錄中彈出最小元素並將其返回。基本的解決方案是使用2個堆棧保持數據逆序排序。這樣我們可以簡單地彈出包含數據的堆棧的頂層元素。但是對此，每個整數的插入都是O（N）。我可以在插入時獲得更好的複雜性，將extractMin操作保持爲O（1）。使用2個堆棧提取O（1）中的Min操作
添加例如使其更清楚：
10，-20,2，-3，-5,10,20（在任何時刻整數流）。
extractMin() // returns -20
extractMin() // returns -5
使用堆棧無法獲得更好的複雜性。即使您要求使用堆棧進行持續提取，但問題的措辭似乎並未明確禁止使用其他數據結構。
在我的答案的早期版本中，我提出了min堆，它通過堆的構建平均具有常量插入（單個插入在最差情況下爲對數）。然而，堆不允許恆定的提取，但僅是對數。
爲了對多個值進行持續提取，您需要對所有值進行排序。一種以比堆棧更好的複雜性實現這一點的方法是構建二叉搜索樹，同時跟蹤最小的節點。使用平衡的bst，可以實現對數插入。爲了獲得恆定的個體提取，還需要在每個節點中存儲父指針。但是如果你只需要遍歷所有的值，那麼你就不需要指針了。
你確定O（1）的平均值？據我瞭解，那麼它可以用於O（n）平均時間比較排序，這可能是不可能的。 – sbarzowski
@sbarzowski（刪除了我以前的評論，以獲得更好的答覆）您是否正確懷疑我的複雜性分析，因爲它們的確可以進行線性排序。插入是[平均contric]（http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity）。但我承諾提取是不變的，但事實並非如此。 – user2079303
我認爲平衡bst（與父鏈接）工作給予分期O（log N）插入（其中N是樹的最大尺寸），但細節非常棘手。尤其是，在彈出序列之後，必須在下一次插入之前重新平衡樹。 –
您可以推送一個數組，然後按排序順序將其彈出，以便排序下限有效。 –
是你的問題，是否有可能通過使用兩個堆棧，或者它可能使用任何合適的數據結構？ – hyde
另外，你是否期望混合插入和彈出，或者先插入一切，然後開始彈出？ – hyde