计算移动最大 [英] Computing a moving maximum

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/12329073/find-the-min-number-in-all-contiguous-subarrays-of-size-l-of-a-array-of-size-n">Find在大小的数组的大小l所有连续的子阵最小数n

我有数字数据的（大型）阵列（大小 N ），并想计算运行最大值与固定窗口大小的数组是W 。

I have a (large) array of numeric data (size N) and would like to compute an array of running maximums with a fixed window size w.

更直接地说，我可以定义一个新的数组出[K-W + 1] = {最大值数据[K-W + 1，...，K]} 为 K＆GT; = W-1 （假设基于0阵列，如C ++）

More directly, I can define a new array out[k-w+1] = max{data[k-w+1,...,k]} for k >= w-1 (this assumes 0-based arrays, as in C++).

有没有更好的方式比 N日志要做到这一点（W）？

[我希望应该有 N A线性的而对的依赖是W ，像搬家平均水平，但无法找到它。对于 N日志（W）我觉得有一种方法来管理一个排序的数据结构，它会做插入（），删除（）和 extract_max（）在日志共（W）或更小尺寸上的结构是W - 就像一个排序二叉树，例如]

[I'm hoping there should be a linear one in N without dependence on w, like for moving average, but cannot find it. For N log(w) I think there is a way to manage with a sorted data structure which will do insert(), delete() and extract_max() altogether in log(w) or less on a structure of size w -- like a sorted binary tree, for example].

非常感谢你。

推荐答案

的确有一种算法，可以在O（N）时间窗口大小W否依赖做到这一点。该想法是使用一个聪明的数据结构支持以下操作：

There is indeed an algorithm that can do this in O(N) time with no dependence on the window size w. The idea is to use a clever data structure that supports the following operations:

• 排队，增加了一个新的元素结构，
• 出列，它去除了最古老的元素从结构和
• 查找-MAX ，返回（但不删除）的最小元素从结构。

• Enqueue, which adds a new element to the structure,
• Dequeue, which removes the oldest element from the structure, and
• Find-max, which returns (but does not remove) the minimum element from the structure.

这基本上是支持的最大元素的访问（但不去除）一个队列数据结构。不可思议的是，在 这个前面的问题看到 ，就可以实现这个数据结构，使得在摊销O（1）时间，所有这些作业运行。其结果是，如果你使用这个结构来排队W¯¯元素，然后连续出队和入队的另一个元素插入结构，同时根据需要调用find-MAX，这将只需要为O（n + Q）时，其中Q是多少查询你做。如果你只关心最低一度每个窗口，这最终是O（N），与窗口大小没有依赖性。

This is essentially a queue data structure that supports access (but not removal) of the maximum element. Amazingly, as seen in this earlier question, it is possible to implement this data structure such that each of these operations runs in amortized O(1) time. As a result, if you use this structure to enqueue w elements, then continuously dequeue and enqueue another element into the structure while calling find-max as needed, it will take only O(n + Q) time, where Q is the number of queries you make. If you only care about the minimum of each window once, this ends up being O(n), with no dependence on the window size.

希望这有助于！

这篇关于计算移动最大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！