java - 为什么使用堆栈容器比较慢？

Question

我正在尝试解决 LeetCode 上的第 739 题“每日温度”。 https://leetcode.com/problems/daily-temperatures/

我的代码使用了JAVA提供的Stack容器。运行需要 60 毫秒。这是我的代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ret = new int[T.length];
        Stack<Integer> stack = new Stack<Integer>();
        for(int i=0; i < T.length; i++){
            while(!stack.isEmpty() && T[i] > T[stack.peek()]){
                int index = stack.pop();
                ret[index] = i - index;             
            }
            stack.push(i);
        }
        return ret;
    }
}

这是一个只需要 6ms 运行的代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {

        int[] temperatures = T;
        if(temperatures == null) return null;

        int[] result = new int[temperatures.length];
        int[] stack = new int[temperatures.length];
        int top = 0;
        stack[top] = -1;

        for(int i = 0; i < temperatures.length; i++) {
            while(stack[top] != -1 && temperatures[i] > temperatures[stack[top]]) {
                int index = stack[top--];
                result[index] = i - index;
            }

            stack[++top] = i;
        }

        return result;
    }
}

为什么使用数组构建堆栈比使用堆栈容器更快？

Answer 1

Java 的 Stack是一个非常的旧类，在 JDK 1.0 中引入。它扩展了 Vector ，并且它的所有数据操作方法都是同步的，从而产生了非常大的性能开销。虽然它没有被正式弃用，但它已经过时了，在这个时代你真的不应该使用它。现代ArrayDeque在没有同步开销的情况下提供相同的功能。