GeeksforGeeks局部极值查找代码存在连续重复值处理缺陷

原局部极值查找代码在处理包含连续重复元素的数组时会出现判断错误：

• 测试用例1：数组[1,2,3,7,11,15,13,12,11,6,5,7,11,8]，原代码可正确识别索引5的15为局部最大值；
• 测试用例2：数组[1,2,3,7,11,15,15,13,12,11,6,5,7,11,8]，由于存在连续的15，原代码错误地将索引4的11标记为局部最大值。

原代码及问题点 #

以下是存在问题的原代码，核心缺陷在于仅比较当前元素的直接相邻元素，当遇到连续重复值时，没有进一步查找更远的有效比较对象：

def findLocalMaximaMinima(n, arr):

    # 存储局部极值索引的列表
    mx = []
    mn = []

    # 判断第一个元素是否为极值
    if(arr[0] > arr[1]):
        mx.append(0)
    elif(arr[0] < arr[1]):
        mn.append(0)

    # 遍历中间元素判断极值
    for i in range(1, n-1):

        # 局部最小值判断（问题点）
        if(arr[i-1] > arr[i] < arr[i + 1]):
            mn.append(i)

        # 局部最大值判断（问题点）
        elif(arr[i-1] < arr[i] > arr[i + 1]):
            mx.append(i)

    # 判断最后一个元素是否为极值
    if(arr[-1] > arr[-2]):
        mx.append(n-1)
    elif(arr[-1] < arr[-2]):
        mn.append(n-1)

    # 输出结果
    if(len(mx) > 0):
        print("局部最大值索引为 : ", end ='')
        print(*mx)
    else:
        print("不存在局部最大值。")

    if(len(mn) > 0):
        print("局部最小值索引为 : ", end ='')
        print(*mn)
    else:
        print("不存在局部最小值。")

修复方案 #

要解决这个问题，我们需要为每个元素找到左侧第一个不等于当前值的元素和右侧第一个不等于当前值的元素，再基于这两个元素进行极值判断：

def findLocalMaximaMinima(n, arr):
    mx = []
    mn = []

    # 处理单个元素的特殊情况
    if n == 1:
        mx.append(0)
        mn.append(0)
    else:
        # 处理第一个元素
        current = arr[0]
        right_idx = 1
        # 找到右侧第一个不同的元素
        while right_idx < n and arr[right_idx] == current:
            right_idx += 1
        if right_idx < n:
            if current > arr[right_idx]:
                mx.append(0)
            elif current < arr[right_idx]:
                mn.append(0)

        # 处理中间元素
        for i in range(1, n-1):
            current = arr[i]
            # 找左侧第一个不同的元素
            left_idx = i - 1
            while left_idx >= 0 and arr[left_idx] == current:
                left_idx -= 1
            # 找右侧第一个不同的元素
            right_idx = i + 1
            while right_idx < n and arr[right_idx] == current:
                right_idx += 1
            
            left_val = arr[left_idx] if left_idx >= 0 else None
            right_val = arr[right_idx] if right_idx < n else None

            is_min = False
            is_max = False
            # 根据左右有效元素判断极值
            if left_val is not None and right_val is not None:
                is_min = left_val > current and current < right_val
                is_max = left_val < current and current > right_val
            elif left_val is not None:
                is_min = left_val > current
                is_max = left_val < current
            elif right_val is not None:
                is_min = current < right_val
                is_max = current > right_val
            
            if is_min:
                mn.append(i)
            elif is_max:
                mx.append(i)

        # 处理最后一个元素
        current = arr[-1]
        left_idx = n-2
        while left_idx >= 0 and arr[left_idx] == current:
            left_idx -= 1
        if left_idx >= 0:
            if current > arr[left_idx]:
                mx.append(n-1)
            elif current < arr[left_idx]:
                mn.append(n-1)

    # 输出结果
    if mx:
        print("局部最大值索引为 : ", end='')
        print(*mx)
    else:
        print("不存在局部最大值。")

    if mn:
        print("局部最小值索引为 : ", end='')
        print(*mn)
    else:
        print("不存在局部最小值。")

修复效果验证 #

用测试用例2验证：
数组[1,2,3,7,11,15,15,13,12,11,6,5,7,11,8]，修复后的代码会正确识别索引5和6的15为局部最大值（左侧为11、右侧为13，满足11<15>13），不会错误标记11为局部最大值。

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