据我了解,这段代码的时间复杂度是 O(N) for循环只会迭代一次,所以时间复杂度为O(N) 但是for循环里面有一个while循环
所以for循环里面嵌套了一个while循环 为什么我们忽略它的时间复杂度?
var dailyTemperatures = function(temperatures) {
let result = new Array(temperatures.length).fill(0);
let stack = [];
for(let i = 0; i < temperatures.length; i++) {
while(stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
let index = stack.pop();
console.log('hello');
result[index] = i - index;
}
stack.push(i);
}
return result;
};
最佳答案
因为 while 循环只是将堆栈元素逐个弹出,并且不能将超过 N 个元素压入堆栈(每个元素压入一次)。因此,即使 while 循环嵌套在 for 循环中,它也不会执行超过 N 次。
关于javascript - 单调栈问题的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69494043/