高效滚动最大和最小窗口

Question

我想有效地计算滚动的最大值和最小值.比每次窗口移动时重新计算所有使用值中的最大值/最小值更好.

这里有一篇帖子提出同样的问题,有人发布了一个涉及某种堆栈方法的解决方案,据说根据其评级工作.但是,对于我的生活,我再也找不到它.

在寻找解决方案或帖子时,我们将不胜感激.谢谢你们!

Answer 1

您要使用的算法称为升序最小值 （C++ 实现）。

要在 C# 中执行此操作，您需要获得一个双端队列类，并且 NuGet 上存在一个名为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;
    }
}