如何查找数组中满足A[j]-A[i]最大且i<j的下标，要求时间复杂度O(n)

核心实现逻辑 #

• 仅需一次遍历即可完成计算，时间复杂度为O(n)，空间复杂度为O(1)，和只求差值的原版实现复杂度完全一致
• 遍历过程中仅需维护4个临时变量：
  • min_idx：记录当前遍历过的区间内，最小元素的下标
  • max_diff：记录当前找到的最大差值，初始值设为负无穷
  • res_left、res_right：记录最大差值对应的两个元素的下标，较小值的下标存在res_left，较大值的下标存在res_right
• 遍历规则（从数组第2个元素开始遍历）：
  1. 先计算当前元素和arr[min_idx]的差值，若该差值大于当前max_diff，则更新max_diff，同时将res_left赋值为min_idx，res_right赋值为当前下标
  2. 再判断当前元素是否小于arr[min_idx]，如果是则更新min_idx为当前下标

注意：必须先计算差值再更新最小下标，避免出现最大差值的两个元素下标顺序颠倒的问题，保证符合「较大元素出现在较小元素之后」的要求。

代码示例（Python） #

def get_max_diff_with_index(arr: list[int]) -> tuple[int, int, int] | None:
    # 数组长度不足2时无法计算差值，直接返回空
    if len(arr) < 2:
        return None
    min_idx = 0
    max_diff = float('-inf')
    res_left = res_right = 0
    for i in range(1, len(arr)):
        # 第一步：计算当前差值，更新最优解
        current_diff = arr[i] - arr[min_idx]
        if current_diff > max_diff:
            max_diff = current_diff
            res_left = min_idx
            res_right = i
        # 第二步：更新当前区间最小元素下标
        if arr[i] < arr[min_idx]:
            min_idx = i
    # 返回值依次为：最大差值、较小元素下标、较大元素下标
    return max_diff, res_left, res_right

# 测试用例
if __name__ == "__main__":
    test_arr = [2, 3, 10, 6, 4, 8, 1]
    print(get_max_diff_with_index(test_arr))  # 输出：(8, 0, 2)

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