时间戳

首页 > 解决方案 > 单调堆栈问题的时间复杂度

javascript - 单调堆栈问题的时间复杂度

问题描述

据我了解，此代码的时间复杂度为 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;
};

标签： javascriptarraysdata-structures

解决方案

因为while循环只是一个一个地弹出堆栈元素，并且在堆栈内推入的元素不能超过N个（每个元素推入一次）。因此，即使 while 循环嵌套在 for 循环中，它也不会执行超过 N 次。

推荐阅读