数组中满足j>i的两元素最大差值优化问题（低于O(n²)复杂度）

给定整数数组，需找出满足j>i的两个元素的最大差值arr[j]-arr[i]，你的O(n²)暴力解法虽能得到正确结果，但数组规模较大时效率极低。以下是两种时间复杂度优于O(n²)的解法，其中线性遍历解法为最优选择：

一、O(n)时间复杂度的线性遍历解法 #

核心思路 #

遍历数组时维护两个关键变量：

• minSoFar：遍历到当前位置时遇到的最小元素（确保它在当前元素左侧，即索引更小）
• maxDiff：当前已找到的最大差值

从左到右逐个处理元素：

1. 对每个元素arr[j]，计算它与minSoFar的差值，若该差值大于maxDiff则更新maxDiff
2. 若当前元素arr[j]比minSoFar更小，则更新minSoFar为当前元素

这种方法仅需一次遍历数组，时间复杂度O(n)，空间复杂度O(1)，是最优解法。

代码实现 #

private static int calculateMaxDiff() {
    int[] arr = {20, 18, 45, 78, 3, 65, 55};
    // 处理数组元素不足2个的边界情况
    if (arr.length < 2) {
        return 0;
    }
    int minSoFar = arr[0];
    int maxDiff = 0;
    for (int j = 1; j < arr.length; j++) {
        // 更新最大差值
        int currentDiff = arr[j] - minSoFar;
        if (currentDiff > maxDiff) {
            maxDiff = currentDiff;
        }
        // 更新当前最小元素
        if (arr[j] < minSoFar) {
            minSoFar = arr[j];
        }
    }
    return maxDiff; // 示例数组返回结果为62
}

验证示例 #

• 对于数组{20,8,45,78,3,65,55}，遍历到8时minSoFar更新为8，后续遇到78时计算78-8=70，这就是符合要求的最大差值。

二、O(nlogn)时间复杂度的分治法 #

核心思路 #

将数组递归拆分为左右两部分，最大差值只会出现在三种情况中：

1. 左半部分内部的最大差值
2. 右半部分内部的最大差值
3. 右半部分的最大值减去左半部分的最小值

递归计算左右两部分的最大差值，再与跨左右的差值比较，取三者中的最大值。这种方法时间复杂度为O(nlogn)，空间复杂度因递归栈为O(logn)，效率不如线性解法，但远优于O(n²)。

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