我有输入数组A.
A[0], A[1], ... , A[N-1]
我希望函数Max(T,A)返回B代表A在大小T所在的前一个移动窗口上的最大值
B[i+T] = Max(A[i], A[i+T])
通过使用最大堆来跟踪当前移动窗口A [i]到A [i + T]的最大值,该算法产生O(N log(T))最坏情况.
我想知道有更好的算法吗？也许是O(N)算法
问题是在长度为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)吗？