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

Question

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

• 推送,在堆栈顶部添加一个新元素,
• 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)

现在,如果我们想查询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.你可以通过利用ArrayList或来轻松地做到这一点LinkedList.或者,您可以使用提供的Java Stack类,但是由于同步可能对此应用程序不必要,因此IIRC会产生一些开销.

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

希望这可以帮助!

编辑:如果你很好奇,我在我的个人网站上有一个min-stack的 C++实现和前面提到的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)