我有一个（大型）数字数据（size N）数组，想计算一个固定窗口大小的运行最大值数组w。
N
w
更直接地，我可以out[k-w+1] = max{data[k-w+1,...,k]}为其定义一个新数组k >= w-1（这与C ++一样，假设是基于0的数组）。
out[k-w+1] = max{data[k-w+1,...,k]}
k >= w-1
有没有比这更好的方法N log(w)呢？
N log(w)
[我希望应该有一个N不依赖的线性变量w，例如移动平均线，但找不到它。因为N log(w)我认为有一种方法可以管理排序的数据结构，该结构可以做到insert()，delete()并且extract_max()完全在log(w)大小结构上w（例如，排序的二叉树），或者更少]。
insert()
delete()
extract_max()
log(w)
非常感谢你。
确实有一种算法可以在O（N）时间内完成此操作，而无需依赖于窗口大小w。这个想法是使用一个聪明的数据结构来支持以下操作：
本质上，这是一个队列数据结构，支持对最大元素的访问（但不删除）。令人惊讶的是，如 先前的问题所示 ，可以实现此数据结构，以使这些操作中的每一个都在O（1）摊销时间内运行。结果，如果使用此结构将w个元素排入队列，然后在需要时调用find- max的同时连续将另一个元素排入队列并排入结构，则将只花费O（n + Q）时间，其中Q是您提出的查询。如果只关心每个窗口的最小值，则最终为O（n），与窗口大小无关。
希望这可以帮助！
