1

您将如何维护堆栈，以便无论何时从堆栈中弹出，您都知道堆栈中的最小元素？算法应该具有恒定的复杂度

提前致谢

4

3 回答 3

3

好的，这是你需要做的..

您需要维护data structure您插入的每个元素的一些包含信息，插入该元素时的值是minimum什么。second minimum

所以，你想要这样的信息： -

对于推送的每个元素 ->

  • 插入后的最小值
  • 插入前的最小值

当您从堆栈中获取该元素时将需要此信息pop。因此，您会知道，无论您是否是popping最小值。如果是，那么您可以用推送此元素之前的值替换当前minimum值。如果不是，minimum value那么届时价值不会有任何变化minimum..

例如：-

假设当前您在堆栈中有以下元素：-

[3, 5, 7, 9, 2, 4]

  • 然后你推入一个值 8 .. 然后你有两个值要维护..（推入 8 之前的最小值，即 2，插入 8 之后的最小值，即 2）：-

    min_value_before_push = min(stack)
push 8
min_value_after_push = min(stack)

  • 如果你推一个值 1，那么minimum_before_insertion是 2，并且minimum_after_insertion是 1： -

    min_value_before_push = 2
min_value_after_push = 1

现在你的堆栈是：-

[1, 8, 3, 5, 7, 9, 2, 4]

现在，如果你pop，你会看到value 1： -

    min_value_before_push = 2
    min_value_after_push = 1

因此，弹出将改变最小值，因此，您将当前最小值更改minimum_value_before_push为 1.. 所以，您的最小值再次为 2..

您当前的堆栈变为：-

[8, 3, 5, 7, 9, 2, 4]

现在，让我们检查一下这个算法是否适用于duplicate元素：-

假设你想再推一个value 2..

min_value_before_push = 2
min_value_after_push = 2

然后你继续pop，你看到 for是 2 value 2，min_value_after_push所以这意味着弹出它会改变最小值。所以你用 替换这个值min_value_before_push，它也是 2。这就是我们想要的。

注意： - 这个算法的一个好处是，你不需要做太多的比较.. 只需与current_minimum_value推时比较.. 与current_minimum_value当你比较pop..

你可以试着继续思考你data structure能拥有什么..

于 2012-09-28T06:26:01.533 回答
2

免责声明：禁止空值（就像 ArrayDeque），并且未经严格测试。 

import java.util.ArrayDeque;

public class PessimisticStack<T extends Comparable<? super T>> {

    private class Entry {
        private Entry(T t, T minNow) {
            this.t = t;
            this.minNow = minNow;
        }
        private final T t;
        private final T minNow;
    }

    private final ArrayDeque<Entry> deque;

    public PessimisticStack() {
        deque = new ArrayDeque<Entry>();
    }

    public PessimisticStack(int initialCapacity) {
        deque = new ArrayDeque<Entry>(initialCapacity);
    }

    public void push(T t) {
        if (t == null) throw new NullPointerException();
        Entry entry = null; 
        if (deque.isEmpty()) {
            entry = new Entry(t, t);
        }
        else {
            T prevMinimum = deque.peek().minNow;
            T newMinimum = null;
            if (t.compareTo(prevMinimum) < 0) {
                newMinimum = t;
            }
            else {
                newMinimum = prevMinimum;
            }
            entry = new Entry(t, newMinimum);
        }
        deque.push(entry);
    }

    public T pop() {
        return deque.pop().t;
    }

    public T getMinimum() {
        Entry entry = deque.peek();
        return (entry == null ? null : entry.minNow);
    }
}

示例用法

PessimisticStack<String> stack = new PessimisticStack<String>();

stack.push("Zebra");
stack.push("Elephant");
stack.push("Bryan");
stack.push("Adam");
stack.push("Calvin");

String calvin = stack.pop();

// "Adam"
System.err.println(stack.getMinimum());

stack.push("Aaron");

// "Aaron"
System.err.println(stack.getMinimum());

String aaron = stack.pop();

// "Adam"
System.err.println(stack.getMinimum());

String adam = stack.pop();

// "Bryan"
System.err.println(stack.getMinimum());
于 2012-09-28T07:12:06.110 回答
1

使用另一个堆栈，比如说minStack，当 push 一个元素时val，检查是否val < minStack.peek()，如果是，也 push valto minStack；当从 中弹出时stack，检查弹出值，例如pop_val，执行minStack.pop()if pop_val == minStack.peek()。

现在我们有了 a可以在特定时间点minStack保存所有local-min-element内容（直到下一次推送到 minStack 的时间），我们可以通过检查堆栈的顶部是否为 a 来轻松确定何时从 minStack 弹出local-min-element，这已经上面已经介绍过了。

但是，只有当所有元素彼此唯一时，该方法才能正常工作，否则会有点困难，提示，使用计数器:)。

于 2012-09-28T06:38:39.760 回答