为什么deque解决了"滑动窗口最大值"问题O(n)而不是O(nk)？

问题是在长度为n的数组中找到大小为k的每个子阵列中的最大值.

蛮力方法是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)之间？即使对于deque解决方案,最坏情况下的时间复杂度实际上是O(kn)吗？

每个元素仅一次添加到双端队列。

因此，弹出操作不能超过元素数O（n）。

有时将检查while条件，而不会弹出，但完成的次数最多等于我们进入while循环的次数（即，两个for循环的迭代次数），即上）。

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