Python实现Max Distance最大间隔算法未通过测试用例原因求解

• 第一版代码错误原因：遍历逻辑存在严重缺陷，对每个下标i仅检查对称位置的j = len(A) - i -1，没有覆盖所有可能的j取值，比如测试用例中的有效组合(i=3, j=4)完全没有被遍历到，自然无法得到正确结果。同时循环范围仅覆盖到len(A)-2，也没有完全遍历所有可能的i值。
• 双循环版本超时原因：两层嵌套循环的时间复杂度为O(n²)，当数组长度超过10^4量级时就会超出时间限制，无法通过大规模测试用例。

我们可以通过预处理辅助数组+双指针的方式将时间复杂度降低到O(n)：

1. 预处理LMin数组：LMin[i]表示数组从开头到下标i范围内的最小值
2. 预处理RMax数组：RMax[j]表示数组从下标j到末尾范围内的最大值
3. 双指针遍历：初始化i=0、j=0、最大差为-1。如果LMin[i] <= RMax[j]，说明存在符合条件的数对，更新最大差后右移j尝试找更大的差值；如果不满足则右移i，尝试找更小的左值。

class Solution:
    def maximumGap(self, A):
        n = len(A)
        if n < 2:
            return -1
        # 预处理左最小值数组
        LMin = [0]*n
        LMin[0] = A[0]
        for i in range(1, n):
            LMin[i] = min(LMin[i-1], A[i])
        # 预处理右最大值数组
        RMax = [0]*n
        RMax[-1] = A[-1]
        for j in range(n-2, -1, -1):
            RMax[j] = max(RMax[j+1], A[j])
        # 双指针遍历
        i = j = 0
        max_diff = -1
        while i < n and j < n:
            if LMin[i] <= RMax[j]:
                max_diff = max(max_diff, j - i)
                j += 1
            else:
                i += 1
        return max_diff if max_diff > 0 else -1

内容的提问来源于stack exchange，提问作者Naga Sai Sriya