使用比O（n）更高效的find-min / find-max进行堆栈？
我有兴趣创build一个类似于支持以下操作的堆栈的Java数据结构，尽可能高效：
- Push，在堆栈顶部添加一个新元素，
- Pop，删除堆栈的顶层元素，
- Find-Max，返回（但不删除）堆栈的最大元素
- Find-Min，返回（但不删除）堆栈的最小元素
这个数据结构最快的实现是什么？ 我怎样才能用Java编写它？
这是一个经典的数据结构问题。 问题背后的直觉如下 – 最大值和最小值可以改变的唯一方法是如果您将新值推入堆栈或从堆栈中popup新值。 考虑到这一点，假设在堆栈中的每个级别都跟踪堆栈中该点的最大值和最小值。 然后，当你将一个新的元素推入堆栈时，可以很容易地（在O（1）时间内）通过比较刚刚推送的新元素与当前最大值和最小值来计算堆栈中任何位置的最大值和最小值。 同样的，当你popup一个元素时，你将暴露堆栈中的元素，在堆栈的其余部分已经存储了最大值和最小值。
在视觉上，假设我们有一个堆栈，并按顺序添加值2,7,1,8,3和9。 我们先推2，然后把2推到栈上。 由于2现在是堆栈中最大最小的值，我们logging下这个：
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到栈顶上存储的caching最小值（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）来完成。
现在，假设我们popup顶部元素。 这产生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的栈的实现，它的渐进性和渐进性是一样的。 我将把练习作为一个练习。 :-)但是，您可能需要考虑使用标准堆栈实现技术之一来实现堆栈，例如使用dynamic数组或链接的对象列表 ，每个对象都包含堆栈元素min，max。 您可以通过利用ArrayList或LinkedList来轻松完成此操作。 或者，您可以使用提供的Java Stack类，尽pipeIIRC由于可能对此应用程序不必要的同步而具有一些开销。
有趣的是，一旦你用这些属性构build了一个栈，就可以将它用作构build块来构build一个具有相同属性和时间保证的队列 。 您也可以在更复杂的构造中使用它来构build具有这些属性的双端队列。
希望这可以帮助！
编辑：如果你好奇，我有我的个人网站上的最小堆栈和上述最小队列的 C ++实现。 希望这可以展示这在实践中可能看起来像什么！
虽然答案是对的，但我们可以做得更好。 如果堆栈有很多元素，那么我们浪费了很多空间。 但是，我们可以把这个无用的空间保存下来：
而不是每个元素保存最小（或最大）的值，我们可以使用两个堆栈。 因为最小（或最大）值的变化不会太频繁，所以只有当新值<= （或>= ）到当前最小值（或最大值）时，才会将最小值（或最大值）值。
这里是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和minStack只有很less的元素，从而节省空间。 例如
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)
可能来不及回复，但只是为了logging。 这是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(); } }
使用链表：
public class MaxMinStack { MaxMinLLNode headMin = null; MaxMinLLNode headMax = null; MaxMinLLNode tailMin = null; MaxMinLLNode tailMax = null; public void push(int data) { MaxMinLLNode node = new MaxMinLLNode(data, null); if (headMin == null) { headMin = node; tailMin = node; } else { if (data < headMin.data) { tailMin = headMin; headMin = node; node.nextNodeReference = tailMin; } } if (headMax == null) { headMax = node; tailMax = node; } else { if (data > headMax.data) { tailMax = headMax; headMax = node; node.nextNodeReference = tailMax; } } } public void pop() { System.out.println("Max Element:" + " " + String.valueOf(headMax.data)); System.out.println("Min Element:" + " " + String.valueOf(headMin.data)); } public void traverse() { MaxMinLLNode ptrMin = headMin; MaxMinLLNode ptrMax = headMax; System.out.println("Min"); while (ptrMin != null) { System.out.println(ptrMin.data); ptrMin = ptrMin.nextNodeReference; } System.out.println("Max"); while (ptrMax != null) { System.out.println(ptrMax.data); ptrMax = ptrMax.nextNodeReference; } } public static void main(String[] args) { MaxMinStack m = new MaxMinStack(); m.push(7); m.push(4); m.push(5); m.push(6); m.push(7); m.push(8); m.push(1); m.push(1); m.push(7); m.push(2); m.push(4); m.push(2); m.traverse(); m.pop(); } } class MaxMinLLNode { int data; MaxMinLLNode nextNodeReference; MaxMinLLNode(int data, MaxMinLLNode node) { this.data = data; this.nextNodeReference = node; } }
