實現一個隊列，其中push_rear（），pop_front（）和get_min（）都是常量時間操作我遇到了這個問題： 實現一個隊列，其中push_rear（），pop_front（）和get_min（）都是常量時間操作。我最初想過使用一個最小堆數據結構，它對于get_min（）具有O（1）復雜度。但是push_rear（）和pop_front（）將是O（log（n））。有誰知道實現這樣一個有O（1）push（），pop（）和min（）的隊列的最佳方法是什么？我搜索了這個，并想指出這個算法極客線程。但似乎沒有一個解決方案遵循所有3種方法的恒定時間規則：push（），pop（）和min（）。感謝所有的建議。
3 回答
夢里花落0921
TA貢獻1772條經驗 獲得超6個贊
您可以使用O（1）pop（），push（）和get_min（）實現堆棧：只需將當前最小值與每個元素一起存儲。因此，例如，堆棧[4,2,5,1]（頂部的1）變為[(4,4), (2,2), (5,2), (1,1)]。
然后，您可以使用兩個堆棧來實現隊列。推到一個堆棧，從另一個堆棧彈出; 如果第二個堆棧在彈出期間為空，則將所有元素從第一個堆棧移動到第二個堆棧。
例如，對于pop請求，從第一個堆棧移動所有元素[(4,4), (2,2), (5,2), (1,1)]，第二個堆棧將是[(1,1), (5,1), (2,1), (4,1)]?，F在返回第二個堆棧的頂部元素。
要查找隊列的最小元素，請查看各個最小堆棧的最小兩個元素，然后取這兩個值中的最小值。（當然，這里有一些額外的邏輯，其中一個堆棧是空的，但這并不難解決）。
這將有O（1）get_min()和push()攤銷O（1） pop()。
添加回答
舉報
0/150
提交
取消