LeetCode 155最小栈：pop方法两种实现差异原因咨询

在实现LeetCode 155题的最小栈时，出现了一个特殊问题：当pop()方法直接比较主栈和辅助栈的栈顶元素时，特定测试用例会失败；但先弹出主栈元素存到变量后再和辅助栈栈顶比较，所有测试用例都能通过。

触发失败的测试用例：

["MinStack","push","push","push","push","pop","getMin","pop","getMin","pop","getMin"]
[[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]]

导致测试失败的代码 #

class MinStack {

    Stack<Integer> s;
    Stack<Integer> auxStack;

    public MinStack() {
        s = new Stack<Integer>();
        auxStack = new Stack<Integer>();
    }
    
    public void push(int val) {
        this.s.push(val);
        if (this.auxStack.empty() || val <= this.auxStack.peek()) {
            this.auxStack.push(val);
        }
    }
    
    public void pop() {
        // 直接用==比较栈顶的Integer对象
        if (this.s.peek() == this.auxStack.peek()) {
            this.auxStack.pop();
        }
        this.s.pop();
    }
    
    public int top() {
        return this.s.peek();
    }
    
    public int getMin() {
        return this.auxStack.peek();
    }
}

可通过所有测试用例的代码 #

class MinStack {

    Stack<Integer> s;
    Stack<Integer> auxStack;

    public MinStack() {
        s = new Stack<Integer>();
        auxStack = new Stack<Integer>();
    }
    
    public void push(int val) {
        this.s.push(val);
        if (this.auxStack.empty() || val <= this.auxStack.peek()) {
            this.auxStack.push(val);
        }
    }
    
    public void pop() {
        // 先弹出主栈元素并自动拆箱为int
        int ans = this.s.pop();
        // 用int和Integer比较，会自动拆箱Integer为int，做值比较
        if (ans == this.auxStack.peek()) {
            this.auxStack.pop();
        }
    }
    
    public int top() {
        return this.s.peek();
    }
    
    public int getMin() {
        return this.auxStack.peek();
    }
}

差异原因 #

核心问题出在Java中Integer类型的==比较逻辑：

• Java为优化性能，对**-128到127之间的Integer值**做了缓存，这个范围内的Integer对象用==比较时，因为指向同一个缓存对象，会返回true。
• 但当数值超出这个范围（比如测试用例里的512、-1024），每次创建的都是新的Integer对象，此时==比较的是对象的引用地址，而非实际数值大小。

失败代码中，this.s.peek() == this.auxStack.peek()直接比较两个Integer对象的引用，当数值超出缓存范围时，即使值相同，引用也不同，导致条件不成立，辅助栈没有弹出对应的最小值，最终getMin()返回错误结果。

通过的代码中：

1. int ans = this.s.pop()会把Integer自动拆箱为int类型，存储实际数值。
2. 后续ans == this.auxStack.peek()比较时，auxStack.peek()返回的Integer会自动拆箱为int，此时比较的是两个数值的大小而非引用，能正确判断值是否相等，辅助栈也会在需要时弹出最小值。

内容的提问来源于stack exchange，提问作者KeshavRathi