尋找最小值與O（1）的時間複雜度堆棧

Question

如何找到與O（1）堆棧的最小值complexity.To找到堆棧的最小值，我發現有兩種方式： 1）分=頂部堆棧值 遍歷堆棧並更新最小值以獲取堆棧的最小值。 這需要O（N）的複雜性，其中N是在堆棧

2）將堆疊元件以minheap ，將被提取將在堆 最小值這需要根值元素的數量O（N日誌（N））

但如何執行O（1）算法，算法是獨立於輸入大小。

這裏的假設是，堆棧已經加載的元素

Answer 1

你不能。用於查找任意堆棧的最小元素的O（1）算法也可以用來查找雙向鏈表的最小元素，然後可以使用該元素創建O（n）排序算法。現在

，有可能實現一個堆棧，因爲它是建立其保持其最小元素的軌道。這樣的堆棧然後可以返回其存儲的最小值，並且如果碰巧彈出最小元素，則只需執行O（n）搜索。但這不是一回事。