单调栈问题时间复杂度为何为O(N)？嵌套while循环为何无需额外计算？

嵌套while循环下时间复杂度仍为O(N)的原因 #

不要直接套用「嵌套循环时间复杂度为两层复杂度相乘」的通用经验，这个结论只成立于每层循环的迭代次数互相独立的场景，这段单调栈代码刚好不符合这个前提。

我们可以从栈操作的总次数入手分析，非常直观：

• 外层for循环遍历数组的每个下标i，每个下标只会执行1次入栈操作stack.push(i)，所有元素的入栈总次数刚好是N（N为温度数组的长度）。
• 内层while循环唯一修改栈的操作是stack.pop()，每个已经入栈的元素最多只会被弹出1次，不可能重复弹出，因此所有元素的出栈总次数最多也只有N次。
• 剩下的逻辑判断、数组赋值、console.log操作都和栈操作绑定，总执行次数不会超过栈操作总次数的2倍，也就是最多2*N次。

你如果做个计数器统计console.log('hello')的总执行次数就会发现，不管输入的温度数组是什么样的，执行次数最多就是N次，不会出现普通冒泡排序那种内层循环每次都跑N次、总次数达到N²的情况。把所有操作的总次数加起来，最高阶的项就是N，因此整体时间复杂度就是O(N)。

对应实现代码如下：

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;
};

内容的提问来源于stack exchange，提问作者Shivam Gupta