Efficient Rolling Max and Min Window

Question

I want to calculate a rolling maximum and minimum value efficiently. Meaning anything better than recalculating the maximum/minimum from all the values in use every time the window moves.

There was a post on here that asked the same thing and someone posted a solution involving some kind of stack approach that supposedly worked based on its rating. However I can't find it again for the life of me.

Any help would be appreciated in finding a solution or the post. Thank you all!

Answer 1

The algorithm you want to use is called the ascending minima (C++ implementation).

To do this in C#, you will want to get a double ended queue class, and a good one exists on NuGet under the name Nito.Deque.

I have written a quick C# implementation using Nito.Deque, but I have only briefly checked it, and did it from my head so it may be wrong!

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;
    }
}