我想有效地计算滚动最大值和最小值。这意味着比每次窗口移动时从使用的所有值重新计算最大值/最小值更好。
这里有一篇文章问了同样的问题,有人发布了一个涉及某种堆栈方法的解决方案,据说该方法是根据其评级来工作的。然而我这辈子都找不到它了。
在寻找解决方案或帖子时提供任何帮助将不胜感激。谢谢你们!
您要使用的算法称为上升最小值 (C++实现) http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html#sliding-window-minimum-algorithm.
要在 C# 中执行此操作,您需要获得双端队列 http://en.wikipedia.org/wiki/Deque类,并且 NuGet 上存在一个好的类,其名称为尼托·德克 http://nuget.org/packages/Nito.Deque/.
我已经使用 Nito.Deque 编写了一个快速的 C# 实现,但我只是简单地检查了它,并且是凭自己的想法完成的,所以它可能是错误的!
public static class AscendingMinima
{
private struct MinimaValue
{
public int RemoveIndex { get; set; }
public double Value { get; set; }
}
public static double[] GetMin(this double[] input, int window)
{
var queue = new Deque<MinimaValue>();
var result = new double[input.Length];
for (int i = 0; i < input.Length; i++)
{
var val = input[i];
// Note: in Nito.Deque, queue[0] is the front
while (queue.Count > 0 && i >= queue[0].RemoveIndex)
queue.RemoveFromFront();
while (queue.Count > 0 && queue[queue.Count - 1].Value >= val)
queue.RemoveFromBack();
queue.AddToBack(new MinimaValue{RemoveIndex = i + window, Value = val });
result[i] = queue[0].Value;
}
return result;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)