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

问题描述

<块引用>

可能的重复:
找出大小为 n 的数组的所有大小为 l 的连续子数组中的最小数

我有一个(大)数字数据数组(大小 N)，并且想计算一个具有固定窗口大小 w 的运行最大值数组.>

更直接，我可以为k定义一个新数组out[k-w+1] = max{data[k-w+1,...,k]}>= w-1(这里假设从 0 开始的数组，就像在 C++ 中一样).

还有比 N log(w) 更好的方法吗?

[我希望 N 中应该有一个线性的，而不依赖于 w，就像移动平均线一样，但找不到它.对于 N log(w) 我认为有一种方法可以使用排序的数据结构来管理 insert(), delete()和 extract_max() 一起在 log(w) 或更少的大小w 的结构上——例如一个排序的二叉树].

非常感谢.

解决方案

确实有一种算法可以在 O(N) 时间内做到这一点，而不依赖于窗口大小 w.这个想法是使用一个聪明的数据结构来支持以下操作:

• 入队，向结构中添加一个新元素，
• 出队，从结构中删除最旧的元素，以及
• Find-max，返回(但不删除)结构中的最小元素.

这本质上是一个队列数据结构，支持访问(但不移除)最大元素.令人惊讶的是，正如在这个较早的问题中所见，可以实现这种数据结构，使得这些操作中的每一个都在分摊 O(1) 时间内运行.因此，如果您使用此结构将 w 个元素​​入队，然后在根据需要调用 find-max 的同时不断出队并将另一个元素入队到该结构中，则只需要 O(n + Q) 时间，其中 Q 是您提出的查询.如果你只关心每个窗口的最小值一次，这最终是 O(n)，不依赖于窗口大小.

希望这有帮助！

Possible Duplicate:
Find the min number in all contiguous subarrays of size l of a array of size n

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.

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++).

Is there a better way to do this than N log(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].

Thank you very much.

解决方案

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:

• 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.

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.

Hope this helps!

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