给定一个未排序的数组 - arr 找到一对 arr[i] 和 arr[j] 使得 arr[i] < arr[j] & i<jand(arr[i] + arr[j])是最大的。

预期时间复杂度——O(n)

,java,arrays,algorithm"/>
时间戳

首页 > 解决方案 > 找到对 (i,j) 使得 i

给定一个未排序的数组 - arr 找到一对 arr[i] 和 arr[j] 使得 arr[i] < arr[j] & i<jand(arr[i] + arr[j])是最大的。

预期时间复杂度——O(n)

java - 找到对 (i,j) 使得 i

给定一个未排序的数组 - arr 找到一对 arr[i] 和 arr[j] 使得 arr[i] < arr[j] & i<jand(arr[i] + arr[j])是最大的。

预期时间复杂度——O(n)

问题描述

给定一个未排序的数组 - arr 找到一对 arr[i] 和 arr[j] 使得 arr[i] < arr[j] & i<jand(arr[i] + arr[j])是最大的。

预期时间复杂度——O(n)

对于数组a = {4, 1, 3, 2, 5, 3}

pair is (4, 5).

这是我尝试过的代码..

void findPair(int[] a){  
        int n = a.length;
        int max = a[0];
        int secondMax = Integer.MIN_VALUE;

        for(int i=1; i<n; i++){
            if(a[i]>max){
                secondMax = max;
                max = a[i];
            }
        }
        if(secondMax == Integer.MIN_VALUE){
            System.out.println("-1 -1");
        }
        else{
            System.out.println(secondMax+" "+max);
        }
}

这是不可能的，你会得到下面的编译时错误。

无法从类型中对非静态方法示例（字符串）进行静态引用

这里（示例）在非静态区域中，主要方法是静态的。

标签： javaarraysalgorithm

解决方案

这是使用堆栈的解决方案。这个想法是堆栈始终包含一个降序，这样对于您查看的每个数字，它都可以与堆栈中低于它的最大数字配对。

使用时将数字弹出是安全的，因为例如，如果您有一个 6 并且堆栈的顶部是 3，则无需保留 3 以防它可以与更大的数字配对；如果以后有 7，您将等待将其与 6 而不是 3 配对。

public void solution(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    int bestX = -1, bestY = -1, bestSum = -1;

    for(int y : arr) {
        while(!stack.isEmpty() && stack.peek() < y) {
            int x = stack.pop();
            if(x + y > bestSum) { bestX = x; bestY = y; bestSum = x + y; }
        }
        stack.push(y);
    }

    System.out.println(bestX + " " + bestY);
}

尽管有嵌套循环，但时间复杂度是 O(n)，因为内部循环总是从堆栈中弹出，并且每个元素只被推送一次，因此只能被弹出一次。

推荐阅读