查找堆棧中的最大值和最小值

假設堆棧中有50000+個整數項？如何有效地找出它的最大值或最小值？堆棧可以增長或減少pop（）和push（），但是我們需要跟蹤堆棧中的最大值和最小值？查找堆棧中的最大值和最小值

2014-10-29 Sharath

什麼是編程語言？如何用數組或鏈表實現堆棧？ – 2014-10-29 09:01:33

你是否需要實現這種堆棧？你有一個堆棧，並希望找到最小和最大？對操作有沒有O（？）限制？你有一些代碼可以分享嗎？ – yossico 2014-10-29 10:53:57

[Stack with find-min/find-max更有效率比O（n）？]（http://stackoverflow.com/questions/7134129/stack-with-find-min-find-max-more-高效超上） – 2014-10-29 12:40:53

我唯一的想法是繼承堆棧並保持最大值和最小值。在彈出和推動做你的最大和最小的變化。

2014-10-29 09:01:24

正如Mischel指出的，Stack with find-min/find-max more efficient than O(n)?已經回答了這個問題。

但是，這種迴應表明，您需要在堆棧中的每個點上存儲每個最大值和最小值。更好的解決方案是爲最大值和最小值分別設置一個堆棧。對於最大堆棧，只有當新元素大於當前最大值時，纔會將新元素推入最大堆棧，反之亦然。當您彈出主堆棧的元素等於它們並且不等於主堆棧中的下一個元素時，您將彈出最小和最大堆棧的元素。

請注意，這需要O（n）額外的空間，同時提供O（1）操作。

2014-10-30 06:57:43 navari

回答