找到最长的可能序列以跳转到下一个更大的数字

Question

伙计们，我想这个问题好几天了，即使我有很多经验，我也没有解决方案。

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

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

我有这个解决方案，但我需要让它更快：

 private static List<Integer> slow(int[] numbers){

        int n = numbers.length;

        int initialJump = 0;
        int next = 0;

        List<Integer> list = new ArrayList<>();

        int counter = 0;
        int maxNum = Arrays.stream(numbers).max().getAsInt();
        for (int i = 0; i < n; i++) {
            initialJump = numbers[i];
            if (initialJump == maxNum) {
                list.add(0);
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                next = numbers[j];
                if (initialJump < next) {
                    counter++;
                    initialJump = next;
                }
            }
            list.add(counter);
            counter = 0;
        }

        return list;
    }

这是示例：

输入

1 4 2 6 3 4

输出

2 1 1 0 1 0

说明

Element 1:
    1 -> 4 -> 6 (2 jumps)
Element 2:
    4 -> 6 (1 jump)
Element 3:
    2 -> 6 (1 jump)
Element 4:
    6 (0 jumps)
Element 5:
    3 -> 4 (1 jump)
Element 6:
    4 -> (0 jumps)

你有什么想法吗？

这是我尝试过的：

private static List<Integer> fast(int[] numbers){
    int n = numbers.length;

    int[] jumplist = new int[n];

    int initialJump = 0;
    int count = 0;
    int maxNum = Arrays.stream(numbers).max().getAsInt();

    Map<Integer, Integer> map = new HashMap<>();

    for(int i=n-1; i>=0; i--) {
        if(i-1 >= 0 && map.get(i+1) != null && numbers[i+1] > numbers[i]){
            jumplist[i] = map.get(i+1)+1;
            continue;
        }

        initialJump = numbers[i];

        if (initialJump == maxNum) {
            jumplist[i] = 0;
            continue;
        }
        for(int j=i; j<n; j++) {
            if(initialJump < numbers[j]) {
                count++;
                initialJump = numbers[j];
                map.put(i,count);
            }
        }
        jumplist[i] = count;
        count = 0;
    }

    return Arrays.stream(jumplist).boxed().collect(Collectors.toList());
}

这是一些测试代码：

        int randomLimit = 50000;
        Random random = new Random();
        List<Integer> randomList = new ArrayList<>();
        for (int i = 0; i < randomLimit; i++) {
            randomList.add(random.ints(0, randomLimit).findFirst().getAsInt());
        }
        System.out.println("Input: " + randomList.stream().limit(20).collect(Collectors.toList()));
        int[] randomArray = randomList.stream().mapToInt(i->i).toArray();

        Instant fastStarts = Instant.now();
        List<Integer> fastRes = fast(randomArray);
        System.out.println(fastRes.stream().limit(20).collect(Collectors.toList()));
        Instant fastEnds = Instant.now();
        System.out.println("fast: " + Duration.between(fastStarts, fastEnds).toMillis());

        Instant slowStarts = Instant.now();
        List<Integer> slowRes = slow(randomArray);
        System.out.println(slowRes.stream().limit(20).collect(Collectors.toList()));
        Instant slowEnds = Instant.now();
        System.out.println("slow: " + Duration.between(slowStarts, slowEnds).toMillis());

        if(slowRes.size() != fastRes.size()){
            System.out.println("Not Equal Result !!");
        }else {
            for (int i = 0; i < slowRes.size(); i++) {
                if (!slowRes.get(i).equals(fastRes.get(i))) {
                    System.out.println("Not Equal Result !!");
                    break;
                }
            }
        }

Answer 1

这是一些优化的代码，但我需要更多优化......

   private static List<Integer> fast(int[] numbers){
        int n = numbers.length;
        int[] jumplist = new int[n];
        Arrays.fill(jumplist, -1);
        int initialJump = 0;
        int count = 0;
        int maxNum = Arrays.stream(numbers).max().getAsInt();

        for(int i=n-1; i>=0; i--) {

            if(i+1 < n && jumplist[i+1] != -1 && numbers[i+1] > numbers[i]){
                jumplist[i] = jumplist[i+1] + 1;
                continue;
            }

            initialJump = numbers[i];
            if (initialJump == maxNum) {
                jumplist[i] = 0;
                continue;
            }
            for(int j=i+1; j<n; j++) {
                if(initialJump < numbers[j]) {
                    count++;
                    initialJump = numbers[j];
                }
            }
            jumplist[i] = count;
            count = 0;
        }

        return Arrays.stream(jumplist).boxed().collect(Collectors.toList());
    }

Answer 2

有什么建议我如何才能实现低于 50 毫秒的时间，现在使用此代码，时间约为 300-400 毫秒。

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

            // partial optimization
            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;
    }