找到堆栈中最大值的优化算法

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