移动窗口的最小值/最大值是否可以达到O（N）？
我有input数组A.
A[0], A[1], ... , A[N-1] 我想要返回B的函数Max（T，A）代表A的大小在上一个大小为T的移动窗口上的最大值
B[i+T] = Max(A[i], A[i+T])
通过使用最大堆来跟踪当前移动窗口A [i]到A [i + T]的最大值，该algorithm产生O（N log（T））最坏的情况。
我想知道有没有更好的algorithm？ 也许是一个O（N）algorithm
O（N）使用Deque数据结构是可能的。 它拥有对（价值;指数）。
at every step: if (!Deque.Empty) and (Deque.Head.Index <= CurrentIndex - T) then Deque.ExtractHead; //Head is too old, it is leaving the window while (!Deque.Empty) and (Deque.Tail.Value > CurrentValue) do Deque.ExtractTail; //remove elements that have no chance to become minimum in the window Deque.AddTail(CurrentValue, CurrentIndex); CurrentMin = Deque.Head.Value //Head value is minimum in the current window
它被称为RMQ（范围最小查询）。 其实我曾经写过一篇文章（用c ++代码）。 请参阅http://attiix.com/2011/08/22/4-ways-to-solve-%C2%B11-rmq/
或者您可能更喜欢维基百科， 范围最小查询
在准备之后，你可以得到O(1)中任何给定范围的最大数目，
