与查找堆叠
我有兴趣创建一个类似于支持以下操作的堆栈的Java数据结构，尽可能高效：
这个数据结构的最快实现是什么？ 我该如何去用Java编写它？
这是一个经典的数据结构问题。 问题背后的直觉如下 - 最大值和最小值可以改变的唯一方式是如果您将新值推入堆栈或从堆栈中弹出新值。 考虑到这一点，假设在堆栈中的每个级别都记录了堆栈中该点的最大值和最小值。 然后，当您将新元素推入堆栈时，您可以轻松地（在O（1）时间内）通过比较刚刚推送的新元素与当前最大值和最小值来计算堆栈中任何位置的最大值和最小值。 类似地，当你弹出一个元素时，你会将堆栈中的元素暴露在顶层之下一层，其中堆栈的其余部分已经存有最大值和最小值。
在视觉上，假设我们有一个堆栈，并按顺序添加值2，7，1，8，3和9。 我们先推2，然后把2推到我们的堆栈上。 由于2现在是堆栈中最大最小的值，因此我们记录下这一点：
2 (max 2, min 2)
现在，让我们推7.由于7大于2（当前最大值），我们最终得出这个结论：
7 (max 7, min 2)
2 (max 2, min 2)
请注意，现在我们可以通过查看堆栈的顶部来查看堆栈的最大值和最小值，并看到7是最大值，2是最小值。 如果我们现在推1，我们会得到
1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)
在这里，我们知道1是最小值，因为我们可以将1与存储在栈顶（2）上的缓存最小值进行比较。 作为练习，确保你明白为什么添加8,3和9后，我们得到这个：
9 (max 9, min 1)
3 (max 8, min 1)
8 (max 8, min 1)
1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)
现在，如果我们想查询最大值和最小值，我们可以在O（1）中通过读取栈顶上存储的最大值和最小值（分别为9和1）来完成。
现在，假设我们弹出顶部元素。 这会产生9并将堆栈修改为
3 (max 8, min 1)
8 (max 8, min 1)
1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)
现在注意到这些元素的最大值是8，正确的答案！ 如果我们再推0，我们会得到这个：
0 (max 8, min 0)
3 (max 8, min 1)
8 (max 8, min 1)
1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)
正如你所看到的，最大值和最小值是正确计算的。
总的来说，这导致了一个具有O（1）push，pop，find-max和find-min的栈的实现，它的渐进性和它所获得的一样好。 我将把练习留作练习。 :-)但是，您可能想要考虑使用标准堆栈实现技术之一来实现堆栈，例如使用动态数组或链接的对象列表，每个对象都包含堆栈元素min，max。 您可以通过利用ArrayList或LinkedList来轻松完成此操作。 或者，您可以使用提供的Java Stack类，尽管IIRC由于可能不需要此应用程序的同步而具有一定的开销。
有趣的是，一旦你用这些属性构建了一个堆栈，你就可以将它用作构建块来构建一个具有相同属性和时间保证的队列。 您也可以在更复杂的构造中使用它来构建具有这些属性的双端队列。
希望这可以帮助！
编辑：如果你好奇，我的个人网站上有一个min-stack和前面提到的min-queue的 C ++实现。 希望这可以展示这在实践中可能看起来像什么！
虽然答案是对的，但我们可以做得更好。 如果堆栈有很多元素，那么我们浪费了很多空间。 但是，我们可以节省这个无用的空间，如下所示：
与每个元素保存min（或max）值不同，我们可以使用两个堆栈。 因为最小（或最大）值的变化不会那么频繁，所以只有当新值<= （或>= ）到当前最小值（或最大值）时，才会将最小值（或最大值）值。
这是Java的实现：
public class StackWithMinMax extends Stack<Integer> {
private Stack<Integer> minStack;
private Stack<Integer> maxStack;
public StackWithMinMax () {
minStack = new Stack<Integer>();
maxStack = new Stack<Integer>();
}
public void push(int value){
if (value <= min()) { // Note the '=' sign here
minStack.push(value);
}
if (value >= max()) {
maxStack.push(value);
}
super.push(value);
}
public Integer pop() {
int value = super.pop();
if (value == min()) {
minStack.pop();
}
if (value == max()) {
maxStack.pop();
}
return value;
}
public int min() {
if (minStack.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return minStack.peek();
}
}
public int max() {
if (maxStack.isEmpty()) {
return Integer.MIN_VALUE;
} else {
return maxStack.peek();
}
}
}
请注意，使用这种方法，我们将有极少数元素minStack ＆ maxStack ，从而节省了空间。 例如
Stack : MinStack : MaxStack
7 7 7
4 4 7
5 1 8 (TOP)
6 1 (TOP)
7
8
1
1
7
2
4
2 (TOP)
可能已经太迟而无法回复，但只是为了记录。 这里是java代码。
import java.util.ArrayList;
import java.util.List;
public class MinStack {
List<Node> items;
public void push(int num) {
if (items == null) {
items = new ArrayList<Node>();
}
Node node = new Node(num);
if (items.size() > 0) {
node.min = Math.min(items.get(items.size() - 1).min, num);
node.max = Math.max(items.get(items.size() - 1).max, num);
} else {
node.min = num;
node.max = num;
}
items.add(node);
printStack();
}
public Node pop() {
Node popThis = null;
if (items != null && items.size() > 0) {
popThis = this.items.get(items.size() - 1);
items.remove(items.size() - 1);
}
printStack();
return popThis;
}
public int getMin() {
if (items != null && items.size() > 0) {
int min = this.items.get(items.size() - 1).min;
System.out.println("Minimum Element > " + min);
return min;
}
return -1;
}
public int getMax() {
if (items != null && items.size() > 0) {
int max = this.items.get(items.size() - 1).max;
System.out.println("Maximum Element > " + max);
return max;
}
return -1;
}
public void printStack() {
int i = 0;
for (Node n : items) {
System.out.print(n.data + " > ");
if (i == items.size() - 1) {
System.out.print(" | Min = " + n.min + " |");
System.out.print(" | Max = " + n.max + " |");
}
i++;
}
System.out.println();
}
public static void main(String args[]) {
MinStack stack = new MinStack();
stack.push(10);
stack.push(13);
stack.push(19);
stack.push(3);
stack.push(2);
stack.push(2);
stack.printStack();
stack.pop();
//stack.getMin();
stack.printStack();
}
}
堆栈类：
class Node {
int data;
int min;
int max;
public Node(int data) {
super();
this.data = data;
}
public Node() {
super();
}
}
上一篇: Stack with find
下一篇: Why Does The Compiler Add An Unnecessary Local Variable