c# - 数组算法中从当前数中找出最大的正确数

Question

我的算法应该从输入的当前数中找到最大正确的数array ，例如，给定以下 int[]输入:

5, 9, 6, 1, 3, 2

我的算法将输出:

9, 6, 3, 3, 2, 2

这是我当前的代码:

public static int[] FindGreatestRightNumber(int[] input)
{
    var output = new int[input.Length];
    for (var i = 0; i < input.Length; i++)
    {
        int maxRightNumber = (i == input.Length - 1 ? input[i] : 0);

        for (var j = i+1; j < input.Length; j++)
        {
            var currentNumber = input[j];
            if (maxRightNumber < currentNumber)
                maxRightNumber = currentNumber;
        }
        output[i] = maxRightNumber;
    }

    return output;
}

有人告诉我它可以更快，如何？有什么想法吗？

更新:请不要使用 LINQ在您的回答中，我想熟悉使用简单代码更快地解决问题的方法，否 LINQ , IEnumerable扩展方法等

Answer 1

您可以从右侧单次传球来完成此操作。诀窍是实现maxRightVal(n) = max(maxRightVal(n+1), values(n+1)):

var output = new int[input.Length];
output[input.Length-1] = input[input.Length-1];

for(int i = input.Length - 2; i >= 0; i--)
    output[i] = output[i+1] > input[i+1] ? output[i+1] : input[i+1];