周五, 3月 4 2016, 4:25:23 下午

从一道算法题看Integer类型的“常量池”

原题：https://leetcode.com/problems/min-stack/

题目本身不难，要求实现一个栈，除了有push(),pop(),top()三个基本功能外，还能够在常数时间复杂度内获得栈内的最小值。

思路很容易，维护两个栈，一个栈保存正常的数据，另一个栈的栈顶一直保持是当前的最小值，代码如下

class MinStack {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        stack.push(x);
        if (minStack.size()==0 || x<=minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (stack.pop()==minStack.peek()){
            minStack.pop();
        }
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

然而，wrong answer了。出错的测试用例是这样：

push(512),push(-1024),push(-1024),push(512),pop,getMin,pop,getMin,pop,getMin

正确的getMin输出结果应该是[-1024,-1024,512]，但是我的结果是[-1024,-1024,-1024]

百思不得其解，代码里怎么都看不出问题在哪，不得已看了别人的答案，思路一模一样的答案里唯一不同的地方在：

public void pop() {
    int x = stack.pop();
    if (x==minStack.peek()){
        minStack.pop();
    }
}

我猜想应该是在==上面出了问题。直接调用pop()的话，返回的是一个Integer类型的对象，而正确的答案里是把返回的对象赋给了一个int变量。难道Integer类型互相之间不能用==来比较吗？但是其他的测试用例为什么又能通过呢？

经过进一步的尝试，我发现数值大于某个数的时候==就不能用了，小于的时候==能正常用，这又是为什么？

网上搜了一圈，终于搞清楚了，在Integer类的源码里有这么一段：

public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

可以看到有一个if判断，IntegerCache.low是写死的-128，IntegerCache.high是可以根据JVM的设置变化的，默认是127。也就是说在-128<=i<=127的范围内，取的是IntegerCache.cache这个数组里的东西，在范围以外就是一个new Integer(i)了，当然就不能用==来比较了。这个IntegerCache.cache就是传说中的常量池。网上有一段对于他的解释：

看一下IntegerCache这个类里面的内容：

private static class IntegerCache {

    private IntegerCache() {

    }

    static final Integer cache[] = new Integer[-(-128) + 127 + 1];

    static {

        for (int i = 0; i < cache.length; i++)

        cache[i] = new Integer(i - 128);

    }

}

由于cache[]在IntegerCache类中是静态数组，也就是只需要初始化一次，即static{……}部分，所以，如果Integer对象初始化时是-128~127的范围，就不需要再重新定义申请空间，都是同一个对象—在IntegerCache.cache中，这样可以在一定程度上提高效率。

回到开头的题目，我们不但可以用上面提到的答案里的写法，也可以用Java里比较两个对象的方法equals()，代码可以这样写：

public void pop() {
    if (stack.pop().equals(minStack.peek())){
        minStack.pop();
    }
}

这回终于accepted了。

还是要多提高自己的姿势水平啊！

留言