java - 在Java中搜索堆栈中最大元素的最快方法是什么？

Question

我遇到一个问题，我必须搜索堆栈中的最大元素。我创建了自己的堆栈类并使用以下方法:

   Node node = top; //created a new node which points to the top of stack

   int max = node.data;  //max contains the value of the top node

   while(node != null) {
           if(node.data > max) {
              max = node.data;
           }
           node = node.next;
    }

   //Print the value of max.

有人可以建议一种更有效的方法吗？

Answer 1

维护两个堆栈:

1. 由所有节点组成。
2. 始终将Max节点保持在其顶部，这样每次都可以更轻松地获取最大元素。

代码如下:

import java.util.Stack;

public class StackWithMax extends Stack<Integer> {

Stack<Integer> s2;

public StackWithMax() {
    s2 = new Stack<Integer>();      
}

public void push(int value){
    if (value >= max()) {
        s2.push(value);
    }
    super.push(value);
}

public Integer pop() {
    int value = super.pop();
    if (value == max()) {
        s2.pop();           
    }
    return value;
}

public int max() {
    if (s2.isEmpty()) {
        return Integer.MIN_VALUE;
    } else {
        return s2.peek();
    }
  }
}