<分区>
Possible Duplicate:
Find the min number in all contiguous subarrays of size l of a array of size n
我有一个(大)数字数据数组(大小 N )，我想计算一个具有固定窗口大小的运行最大值数组 w .
更直接地说，我可以定义一个新数组 out[k-w+1] = max{data[k-w+1,...,k]}对于 k >= w-1 (这假设数组从 0 开始，就像在 C++ 中一样)。
有没有比 N log(w) 更好的方法呢？ ？
[我希望 N 中应该有一个线性的不依赖w ，就像移动平均线，但找不到它。对于 N log(w)我认为有一种方法可以使用排序的数据结构进行管理 insert() , delete()和 extract_max()一共在log(w)或小于 w 的结构-- 例如，像排序的二叉树]。
非常感谢。