为什么对“滑动窗口最大值”采用双端队列解决方案？问题O（n）而不是O（nk）？ [英] Why is the deque solution to the "Sliding Window Maximum" problem O(n) instead of O(nk)?

问题描述

问题在于找到长度为n的数组中每个大小为k的子数组的最大值。

The problem is to find the maximum in each subarray of size k in an array of length n.

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

The brute force method is O(nk). But using a deque, the solution is supposedly O(n). However I am not convinced that it gets to O(n), in particular because of this while loop:

# 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）？

which is inside of a for loop from k to n. Couldn't this technically run up to k times each loop, giving somewhere between O(n) and O(kn)? Is the worst-case time complexity actually O(kn) even for the deque solution?

推荐答案

每个元素都添加到双端队列恰好一次。

Every element is added to the deque exactly once.

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

Thus you can't have more pop operations than the number of elements, which is O(n).

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

The while condition will sometimes be checked without a pop, but the number of times that is done is at most equal to the number of times we get to the while loop (that is, the number of iterations of both for loops), which is O(n).

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

The rest of the code is also O(n), thus the total running time is O(n+n+n) = O(n).

这篇关于为什么对“滑动窗口最大值”采用双端队列解决方案？问题O（n）而不是O（nk）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！