找到堆棧中最大值的優化算法

Question

Stack<Integer> st= new Stack<Integer>(); 
    int max=(int) st.peek(); 
    int top=0; 
    for(Integer loopVal:st) 
    { 
    if(max<loopVal) 
     max=loopVal; 
    } 
    System.out.println(max); 

這個代碼在堆棧中找到最大值，工作得很好，但我希望優化其性能，以便它可以處理非常大的堆棧。有人可以提出更好的算法嗎？

Answer 1

算法的複雜性O(n) - 線性。在找到最大值之前，您需要處理所有元素。對於給定的數據結構，您將不會獲得更好的複雜性。

唯一的選擇是有Sorted數據結構，其中元素是有序的。這使得您可以通過O(1)複雜性獲得最大值，但排序本身需要O(n*log(n))，如果您只需要獲取最大元素，這是沒有意義的。

Answer 2

沒有辦法在非線性時間內從堆棧中獲取最大值。實際上，堆棧中的元素不必具有可比性，因此每個T都不存在max的概念，您可以將其放入Stack。

你可以推出自己的實現，它適用於Comparable<T>，或者只是維護兩個堆棧的元素，一個元素和另一個最大元素，最大堆棧將保持當前最大值，當你彈出時，兩個堆棧。

Answer 3

O（n）是在搜索堆棧中的最大元素時可以獲得的最佳時間複雜度，因爲最大元素可以位於堆棧中的任何位置。你可以做的一件事就是製作堆棧，也就是將元素插入堆棧時將值與最大變量進行比較，如果插入的值大於最大變量值，則更新最大變量。插入也需要線性時間，但它仍然比在堆疊完成後單獨找到最大元素要好。這種方法的問題在於，如果您從堆棧中彈出元素，您可能會在某個時候彈出max元素，並且知道如何在不掃描堆棧的情況下查找新的最大值。

Answer 4

根據您的實際需求，您可以進行另一種折衷。

在1個Integer對象的存儲成本，你可以用複雜性讓您的最大值O（1）不排序，用O（1）成本PUSH與爲O（n）成本時從堆棧中彈出元素。

public class IntStackWithMax { 

    private Integer maxVal = Integer.MIN_VALUE; 
    private Vector<Integer> values = new Vector<Integer>(); 

    // cost O(1) 
    public Integer getMaxVal() { 
     return maxVal; 
    } 

    //cost O(1) 
    public boolean push(Integer item) { 
     maxVal = Math.max(maxVal, item); 
     return values.add(item); 
    } 

    //cost O(n) (!!!) 
    public Integer pop() { 
     Integer result = values.remove(values.size() - 1); 
     maxVal = Collections.max(values); 
     return result; 
    } 

    //cost O(1) 
    public Integer peek() { 
     return values.lastElement(); 
    } 
} 

也請注意，這是不線程安全的。

Answer 5

如果空間複雜度會受到影響，你可以創建另一個堆棧和繼續推動最小值當過你推一個新的最低到原來的堆...

Refer this for more implementation details