algorithm - 为什么 "Sliding Window Maximum"问题的deque解是O(n)而不是O(nk)？

Question

问题是find the maximum in each subarray of size k in an array of length n .

蛮力法是O(nk)。但是使用双端队列，解决方案据说是 O(n)。但是我不相信它会达到 O(n)，特别是因为这个 while 循环:

# Remove all elements smaller than 
# the currently being added element  
# (Remove useless elements) 
while Qi and arr[i] >= arr[Qi[-1]] : 
    Qi.pop()

这是从 k 到 n 的 for 循环内部。这在技术上不能每次循环运行 k 次，在 O(n) 和 O(kn) 之间？即使对于双端队列解决方案，最坏情况下的时间复杂度实际上是 O(kn) 吗？

Answer 1

可以分两步分别统计while循环中进行比较的次数，然后相加。这也将是 while 循环的总迭代次数，并且由于每次迭代花费的时间是恒定的，因此它也将是 while 循环的总运行时间。

真实比较

如果 Qi and arr[i] >= arr[Qi[-1]] 为真，也会有弹出操作(因为这是在 while 循环体中)。

每个元素只添加到双端队列一次。因此，弹出操作的数量不能超过元素的数量，即 O(n)。

因此这些比较的总数也是 O(n)。

虚假比较

Qi and arr[i] >= arr[Qi[-1]] 也可以为 false，但这只会在我们每次进入 while 循环时发生一次(因为，如果如果为假，循环将停止，并继续执行后续代码。

我们到达while循环的次数等于两个for循环的迭代次数，即O(n)。

因此这些比较的总数也是 O(n)。

总运行时间

其余代码也是 O(n)，因此总运行时间为 O(n+n+n) = O(n)。