java - 找到 (i,j) 对，使得 i<j 并且 (a[i] + a[j]) 最大

Question

给定一个未排序的数组 - arr 找到一对 arr[i] 和 arr[j] 使得 arr[i] < arr[j] & i<j和(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);
        }
}

Answer 1

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

在使用时将数字弹出是安全的，因为例如如果你有一个 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)，因为内层循环总是从堆栈中弹出，并且每个元素只被压入一次，因此只能弹出一次。