求优化C#最长合法跳跃序列算法，使其运行耗时低于50毫秒

问题定义 #

给定一组数字序列，需计算每个数字出发的最长合法跳跃序列，规则如下：

• 仅能跳到比当前数字更大的数；
• 仅当当前数字与目标数字之间没有更大值时，才可跳跃；
• 仅能从左向右跳跃。
  要求将算法运行耗时降至50毫秒以下。

现有C#实现 #

static int[] fast(string inputNumbers)
{
    var numbers = inputNumbers.Trim().Split().Select(int.Parse).ToArray();
    var numN = numbers.Length;

    var jumpList = new int[numN];
    var initialJump = 0;
    int counter = 0, max = numbers.Max();

    for (int i = numN - 1; i >= 0; i--)
    {
        if (i + 1 < numN && numbers[i] < numbers[i + 1])
        {
            jumpList[i] = jumpList[i + 1] + 1;
            continue;
        }

        initialJump = numbers[i];

        if (initialJump == max)
        {
            continue;
        }

        for (int j = i + 1; j < numN; j++)
        {
            if (initialJump == max)
            {
                break;
            }

            if (initialJump < numbers[j])
            {
                counter++;
                initialJump = numbers[j];
            }
        }

        jumpList[i] = counter;
        counter = 0;
    }

    return jumpList;
}

现有实现的性能瓶颈 #

当前算法在最坏场景（如严格递减序列）下时间复杂度为O(n²)，每个元素需要遍历后续所有元素统计跳跃次数，当序列长度较大时（如10^5级别），耗时会远超50ms。

优化方案：单调栈+动态规划 #

利用单调递减栈预处理每个元素的「下一个更大元素（NGE）」索引，再通过动态规划从右往左推导每个位置的最长跳跃序列长度，整体时间复杂度降至O(n)，完全满足50ms的性能要求。

核心思路 #

1. 单调栈预处理NGE：遍历序列时维护一个单调递减的栈，栈中存储元素索引。对于每个元素，弹出栈中所有小于当前元素的索引，栈顶剩余的索引即为当前元素的下一个更大元素的位置；
2. 动态规划计算长度：从右往左遍历，若当前元素存在下一个更大元素，则当前位置的最长序列长度 = 1 + 下一个更大元素的长度；若不存在，则长度为0。

优化后的C#代码 #

static int[] OptimizedLongestJumpSequence(string inputNumbers)
{
    var numbers = inputNumbers.Trim().Split().Select(int.Parse).ToArray();
    int n = numbers.Length;
    if (n == 0) return Array.Empty<int>();

    // 预处理每个元素的下一个更大元素索引，初始为-1表示无
    int[] nextGreaterIndex = new int[n];
    Array.Fill(nextGreaterIndex, -1);
    Stack<int> stack = new Stack<int>();

    for (int i = 0; i < n; i++)
    {
        // 维护单调递减栈，弹出所有小于当前元素的索引
        while (stack.Count > 0 && numbers[stack.Peek()] < numbers[i])
        {
            int idx = stack.Pop();
            nextGreaterIndex[idx] = i;
        }
        stack.Push(i);
    }

    // 动态规划计算最长跳跃序列长度
    int[] result = new int[n];
    // 从右往左遍历
    for (int i = n - 2; i >= 0; i--)
    {
        if (nextGreaterIndex[i] != -1)
        {
            // 当前元素的最长序列 = 1（跳到下一个更大元素） + 该元素的最长序列
            result[i] = 1 + result[nextGreaterIndex[i]];
        }
        // 无下一个更大元素时，结果保持0
    }

    return result;
}

性能说明 #

• 单调栈遍历仅需O(n)时间：每个元素入栈和出栈各一次；
• 动态规划遍历同样为O(n)时间；
• 整体算法的时间复杂度为O(n)，空间复杂度为O(n)（栈和辅助数组），对于百万级别的序列也能轻松在50ms内完成计算。

内容的提问来源于stack exchange，提问作者user23269262