如何优化Python代码以在3秒内解决最小连续子列表难度差问题？

问题背景 #

Dan有一组题目，题目难度存储在整数列表a中，第i个题目的难度为a[i]。需从列表中选择至少两个题目，且只能选择连续子列表（即列表中的一段连续元素）。目标是选出难度差异尽可能小的题目，求满足条件的连续子列表中，最大难度与最小难度的最小差值。

输入输出要求 #

• 输入：以单个空格分隔的整数列表a
• 输出：可达到的最小难度差值

约束条件 #

• 2 ≤ len(a) ≤ 500000
• 1 ≤ a[i] ≤ 10^9
• 时间限制：3秒

示例 #

• 输入：10 6 9 1
• 输出：3

我的代码 #

import time # 导入时间模块
arr = list(map(int, input().split(" ")))

st = time.time()
diff = 10**9
for i in range(len(arr)-1):
    max_ele = min_ele = arr[i]
    for j in range(i+1, len(arr)):
        max_ele = max(max_ele, arr[j])
        min_ele = min(min_ele, arr[j])
        if max_ele - min_ele <= diff:
            diff = max_ele - min_ele
    
print(diff)
# end = time.time() - st
#print(end)

代码优化方案 #

你的原始代码是O(n²)时间复杂度，当n达到50万时，计算量会突破2.5e11次，完全不可能在3秒内跑完。必须将复杂度降到O(n)级别才能满足要求。

核心思路 #

实际上，最小的难度差值必然出现在长度为2的连续子列表中。原因很简单：如果存在一个长度≥3的连续子列表，其最大最小差为d，那么这个子列表中必然存在一对相邻元素的差值≤d——如果所有相邻元素的差值都大于d，整个子列表的最大最小差会是这些差值的总和，必然大于d。因此，我们只需要计算所有相邻元素的差值，取最小值即可。

优化后的代码 #

import time

arr = list(map(int, input().split()))
st = time.time()

min_diff = float('inf')
for i in range(len(arr)-1):
    current_diff = abs(arr[i] - arr[i+1])
    if current_diff < min_diff:
        min_diff = current_diff
        # 提前终止：找到差值为0时直接退出，不可能有更小的结果
        if min_diff == 0:
            break

print(min_diff)
# print(time.time() - st)

关键优化点 #

1. 时间复杂度降至O(n)：仅需遍历数组一次，50万次计算在Python中可轻松在0.1秒内完成
2. 输入处理优化：input().split()默认按任意空白符分割，比split(" ")更健壮，能处理多个空格的情况
3. 提前终止逻辑：当找到差值为0的情况时直接break，避免不必要的计算
4. 通用初始化：用float('inf')初始化最小差值，避免因题目中数值范围变化导致初始化值不够大的问题

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