找到最长可能的跳跃序列

Question

这个问题我想了好几天了，没有解决。我设法进行了优化，使代码执行时间约为 300-400 毫秒。我的任务是让它低于 50ms。

给定一个数字序列，计算每个数字的最长可能的跳跃序列。

• 您只能跳到大于当前数字的数字上。
• 您可以跳过一个数字，前提是两者之间没有更大的值。
• 您只能从左向右跳跃。

我有这个解决方案：

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++)
        {
            // There is no need to iterate other numbers if max is reached (skip iterations)
            if (initialJump == max)
            {
                break;
            }

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

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

    return jumpList;
}

Java 也有类似的问题： Find 最长的可能序列以跳转到下一个更大的数字

我正在用 C# 编写解决方案。

Answer 1

由于有内部循环，算法的时间复杂度为 O(𝑛²)。这可以以 O(𝑛) 时间复杂度完成。

技巧是使用一个堆栈，该堆栈将在向后迭代中访问数字时按降序跟踪数字。每当一个值不小于堆栈顶部时，该顶部元素就会从堆栈中弹出。该值/索引的跳转次数对应于堆栈的大小，因为堆栈将包含您可以跳转到的值。

这是使用此堆栈功能调整的代码：

using System.Collections.Generic;

// ...

    static int[] fast(string inputNumbers)
    {
        var numbers = inputNumbers.Trim().Split().Select(int.Parse).ToArray();
        var jumpList = new int[numbers.Length];
        Stack<int> stack = new Stack<int>();
        for (int i = numbers.Length - 1; i >= 0; i--)
        {
            while (stack.Count > 0 &&  numbers[i] >= stack.Peek()) {
                stack.Pop();
            }
            jumpList[i] = stack.Count;
            stack.Push(numbers[i]);
        }

        return jumpList;
    }

由于一个值只能从堆栈中压入和弹出一次，因此时间复杂度为 O(𝑛)。