使用 find-min/find-max 进行堆栈比 O(n) 更高效？

Question

我有兴趣创建一个类似于堆栈的Java数据结构，它尽可能高效地支持以下操作：

• Push，它在堆栈顶部添加一个新元素，
• Pop，它删除堆栈顶部的元素，
• Find-Max，它返回（但不删除）堆栈的最大元素，
• Find-Min，返回（但不删除）堆栈的最小元素，以及

此数据结构的最快实现是什么？我该如何用 Java 编写它？

Answer 1

这是一道经典的数据结构题。问题背后的直觉如下 - 最大值和最小值可以改变的唯一方法是将新值推入堆栈或从堆栈中弹出新值。鉴于此，假设在堆栈中的每个级别，您都跟踪堆栈中该点或低于该点的最大值和最小值。然后，当您将新元素压入堆栈时，您可以通过将刚刚压入的新元素与当前的最大值和最小值进行比较，轻松（在 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) 中完成此操作和 min 位于堆栈顶部（分别为 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) 的入栈、出栈、find-max 和 find-min，这是渐近所能达到的最佳效果。我将把实施作为练习。 :-) 但是，您可能需要考虑使用一种标准堆栈实现技术来实现堆栈，例如使用 动态数组或对象的链接列表，每个对象都保存堆栈元素，最小值，和最大。您可以通过利用 ArrayList 或 LinkedList 轻松完成此操作。或者，您可以使用提供的 Java Stack 类，尽管 IIRC 由于同步而产生一些开销，而该应用程序可能不需要这些开销。

有趣的是，一旦您使用这些属性构建了堆栈，您就可以将其用作构建块来构建 具有相同属性和时间保证的队列。您还可以在更复杂的构造中使用它来构建具有这些属性的双端队列。

编辑：如果你好奇，我有 最小堆栈和前面提到的min-queue 在我的个人网站上。希望这能展示这在实践中可能是什么样子！

Answer 2

虽然答案是正确的，但我们可以做得更好。如果堆栈有很多元素，那么我们就浪费了很多空间。但是，我们可以按如下方式保存这些无用的空间：

我们可以使用两个堆栈，而不是保存每个元素的最小值（或最大值）。因为最小值（或最大值）的变化不会那么频繁，所以只有当新值是 <=（或 >=) 到当前的最小值（或最大值）。

下面是 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)     

Answer 3

可能来不及回复，但只是为了记录。这是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();
        }
    }

Answer 4

使用链接列表：

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;
    }
}