解决方法@H_404_8@

您要使用的算法称为升序最小值 (C++ implementation).

要在C#中执行此操作,您将需要获得double ended queue类,并且在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;
    }
}