使用 find-min/find-max 的堆栈比 O（n） 更有效？

这是一个经典的数据结构问题。问题背后的直觉如下 - 最大值和最小值可以更改的唯一方法是将新值推送到堆栈上或从堆栈中弹出新值。鉴于此，假设在堆栈中的每个级别，您都跟踪堆栈中该点处或以下的最大值和最小值。然后，当您将新元素推送到堆栈上时，您可以通过将刚刚推送的新元素与当前最大值和最小值进行比较，轻松地（在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)

现在，如果我们想查询 max 和 min，我们可以在 O（1） 中通过读取堆栈上存储的 max 和 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）push，pop，find-max和find-min的堆栈的实现，这在渐近上是尽可能好的。我将把实现作为一个练习。:-)但是，您可能需要考虑使用标准堆栈实现技术之一来实现堆栈，例如使用对象的动态数组或链接列表，每个对象都包含堆栈元素 min 和 max。您可以通过利用 off 或 来轻松完成此操作。或者，您可以使用提供的 Java 类，尽管 IIRC 由于同步，它会产生一些开销，而此应用程序可能不需要同步。ArrayListLinkedListStack

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

希望这有帮助！

编辑：如果你很好奇，我已经在我的个人网站上C++了min-stack和前面提到的min-queue的实现。希望这能展示这在实践中可能是什么样子！

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

我们可以使用两个堆栈，而不是为每个元素保存最小（或最大）值。由于最小值（或最大值）的变化不会那么频繁，因此只有当新值为（或）当前最小值（或最大值）值时，我们才会将最小值（或最大值）推送到其各自的堆栈。<=>=

下面是 中的实现：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();
        }
    }
}

请注意，使用这种方法，我们在 & 中将只有很少的元素，从而节省空间。例如：minStackmaxStack

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)