Python实现UVA 11078超时，此代码真的低效吗？

问题背景 #

问题要求找出给定整数列表中满足i<j时a[i]-a[j]的最大值。输入规则为：先给定测试用例数T，每个测试用例先输入数字个数n，再输入n个整数。原代码逻辑上是O(n)时间复杂度，但提交UVA时出现超时错误。

原代码 #

import math

T = int(input())
for _ in range(T):
    n = int(input())
    diff = -math.inf

    score = int(input()) # Using the very first input as max and min
    max = score
    min = score
    for i in range(1,n):
        score = int(input())
        if max - score > diff:
            diff = max - score
        if score > max:
            max = score
        if score < min:
            min = score
    print(diff)

超时原因 #

Python中频繁调用input()会产生较高的IO开销，当测试用例数据量较大时，多次IO交互会导致程序运行超时。此外，原代码中维护的min变量完全无用，属于多余的计算开销。

优化方案 #

核心优化：批量读取输入 #

一次性读取所有输入内容，避免多次调用input()的IO开销，将输入数据转换为整数列表后，通过指针遍历处理，大幅提升效率。

简化逻辑：移除无用变量 #

只需要维护遍历到当前位置之前的最大值（因为要满足i<j，每个j对应的最优i是j之前的最大a[i]），无需维护最小值。

优化后的代码 #

import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    ptr = 0
    T = data[ptr]
    ptr += 1
    for _ in range(T):
        n = data[ptr]
        ptr +=1
        max_val = data[ptr]
        ptr +=1
        max_diff = -float('inf')
        for _ in range(n-1):
            current = data[ptr]
            ptr +=1
            if max_val - current > max_diff:
                max_diff = max_val - current
            if current > max_val:
                max_val = current
        print(max_diff)

if __name__ == "__main__":
    main()

说明 #

1. 使用sys.stdin.read()一次性读取所有输入，分割为整数列表后，通过指针ptr跟踪当前处理位置，彻底避免多次IO操作。
2. 移除无用的min变量，减少不必要的条件判断，进一步提升执行效率。
3. 用-float('inf')替代math.inf，无需导入math模块，简化依赖。

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