Python双指针法判断山谷列表的代码问题修正

判定规则 #

• 列表元素从起始位置开始严格递减，到达唯一谷底点后转为严格递增，即为合法山谷列表
• 合法示例序列：9,6,5,4,10,13,40,55,68
• 强制实现要求：必须使用双指针法完成判定，需兼容谷底位置不对称、左右两侧元素数量不等的场景

原有代码缺陷 #

原有实现采用首尾指针同步步进的逻辑，强制要求左右两侧同时满足递减、递增判定条件，仅当谷底恰好位于列表中点、两侧元素数量完全相等时能输出正确结果，无法处理谷底偏左或偏右的场景，例如10,5,3,4,6,7,8这类谷底左侧仅2个元素、右侧有4个元素的合法山谷序列，会被原有代码误判为非山谷列表。

修正后双指针实现逻辑 #

双指针不需要强制同步步进：

1. 左指针从列表最左端出发，只要相邻元素满足严格递减就持续右移，直到走到递减段的终点（即谷底候选位置）停止
2. 右指针从列表最右端出发，只要相邻元素满足严格递增就持续左移，直到走到递增段的终点（即谷底候选位置）停止
3. 最终校验两个指针是否相遇在同一个位置，且该位置不是列表首尾（排除纯递减、纯递增的非山谷序列），即可得出判定结果

修正后可运行代码 #

def isValley(n):
    arr_length = len(n)
    # 序列长度不足3时，不可能形成先减后增的山谷结构
    if arr_length < 3:
        return False
    left = 0
    right = arr_length - 1

    # 左指针遍历完左侧严格递减段
    while left < arr_length - 1 and n[left] > n[left + 1]:
        left += 1
    
    # 右指针遍历完右侧严格递增段
    while right > 0 and n[right] > n[right - 1]:
        right -= 1
    
    # 双指针相遇在同一谷底，且谷底不在首尾位置即为合法山谷
    return left == right and left != 0 and right != arr_length - 1

# 交互逻辑
n = list(map(int, input("Enter the numbers : ").split()))
print(n)
print("Valley" if isValley(n) else "Not a valley")

效果验证 #

• 对称谷底场景：输入9 6 5 4 10 13 40 55 68，正确输出Valley
• 不对称谷底场景：输入10 5 3 4 6 7 8（谷底偏左）、20 15 10 5 2 6 9 11（谷底偏右），均正确输出Valley
• 非法场景：纯递减序列10 9 8 7、纯递增序列1 2 3 4、存在相等元素的非严格序列7 3 3 5，均正确输出Not a valley

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