为什么我在 return Minstack.peek(); 行上收到空堆栈错误

Question

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> Minstack;

    public MinStack() {
        stack = new Stack();
        Minstack = new Stack();

    }

    public void push(int val) {
        stack.push(val);

        int min = val;

        if (Minstack.isEmpty()) {
            Minstack.push(min);
        }

        else {
            if (Minstack.peek() > min) {
                Minstack.push(min);
            }
        }
    }

    public void pop() {
        int val = stack.pop();

        if (Minstack.peek() == val) {
            Minstack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return Minstack.peek(); <----------------------------------- HERE
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

我已经尝试过使用 2 个堆栈（其中包含 stack 和 minstack）的我自己的代码，其中我仅推送当前最小值

但是在给定的测试用例中我想知道为什么堆栈是空的？因为我已经确保从一开始就推动最小值

这是测试用例

Answer 1

这个想法是始终维护两个“并行”堆栈 - 每次将元素压入堆栈时，都必须压入当前最小值，当您弹出堆栈时，当然也会弹出最小值。这样，您就可以始终保持最新的最小值。

在代码中，您有条件地推送和弹出到最小堆栈，这意味着两个堆栈将不同步。您不应该检查是否应该弹出或压入堆栈，而应该检查您要压入或弹出的值：

 public void push(int val) {
    stack.push(val);

    // Check if val is the new minimum
    // If it is - push it.
    // If it isn't, re-push the current mimum

    int min = val;
    if (!instack.isEmpty() && minstack.peek() < min) {
        min = minstack.peek();
    }
    minstack.push(min);
}

public void pop() {
    // Pop both stacks
    stack.pop();
    minstack.pop();
}