假設堆棧中有50000+個整數項?如何有效地找出它的最大值或最小值? 堆棧可以增長或減少pop()和push(),但是我們需要跟蹤堆棧中的最大值和最小值?查找堆棧中的最大值和最小值
0
A
回答
0
我唯一的想法是繼承堆棧並保持最大值和最小值。在彈出和推動做你的最大和最小的變化。
1
正如Mischel指出的,Stack with find-min/find-max more efficient than O(n)?已經回答了這個問題。
但是,這種迴應表明,您需要在堆棧中的每個點上存儲每個最大值和最小值。更好的解決方案是爲最大值和最小值分別設置一個堆棧。對於最大堆棧,只有當新元素大於當前最大值時,纔會將新元素推入最大堆棧,反之亦然。當您彈出主堆棧的元素等於它們並且不等於主堆棧中的下一個元素時,您將彈出最小和最大堆棧的元素。
請注意,這需要O(n)額外的空間,同時提供O(1)操作。
相關問題
- 1. 查找最小值和最大值JAVA
- 2. 查找最大,最小和中間值
- 3. 在Java中查找num值和最小值/最大值值
- 4. 在bigquery中查找多個值的最小值和最大值
- 5. 查找值的平均值,最大值和最小值進入
- 6. 查找最大值/最小值
- 7. 查找局部最小值/最大值
- 8. SQL查詢 - 查找日常最小值,最大值和時間的最小值和最大值發生
- 9. 在clojure中查找一棵樹的最大值和最小值
- 10. 如何查找列表框中的最大值和最小值
- 11. 如何找到最大堆棧大小?
- 12. 查找最大羣集的最小值?
- 13. MongooseJS查找最大值,最小值和平均值
- 14. 在SQL中查找局部最大值和局部最小值
- 15. 從bash數組中查找最大值和最小值
- 16. 在WPF DataGrid列中查找最大值和最小值
- 17. 查找最大值和最小值爲偶數和奇數
- 18. 最大值和最小值?
- 19. 查找無ARRAY最小值和最大值的Java
- 20. 查找數組的最小值和最大值
- 21. 查找最大值和最小值每N行的CSV數據
- 22. 查找長矢量的最小值和最大值
- 23. Js:查找可能的變量最大值和最小值
- 24. Haskell ::查找一組元組的最小值和最大值
- 25. 中的std ::最大值和最小值
- 26. 查找最大的5值小於1,最小的5個值
- 27. 如何查找最大值和最小值
- 28. 如何使用nCr查找最小值和最大值?
- 29. Unix腳本 - 查找最小值和最大值(Bash Shell)
- 30. 使用CUBLAS查找最大值和最小值
什麼是編程語言?如何用數組或鏈表實現堆棧? – 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