我正在尝试解决 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;
}
}
这是一个只需要 6 毫秒即可运行的代码:
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;
}
}
为什么使用数组构建堆栈比使用堆栈容器更快?
最佳答案
Java 的 Stack
是一个非常古老的类,在 JDK 1.0 中引入。它延伸Vector
,并且它的所有数据操作方法都是同步的,从而产生了非常大的性能开销。虽然它没有被正式弃用,但它已经过时了,你真的不应该在当今时代使用它。现代ArrayDeque
提供相同的功能而无需同步开销。
关于java - 为什么使用堆栈容器速度较慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54002081/