Python处理立方体序列时while循环仅执行一次迭代问题求解

问题排查 #

你的代码存在两个核心逻辑错误，导致运行结果不符合预期：

1. 索引判断逻辑错误 #

Python中deque.index()方法只会返回元素第一次出现的非负整数索引，找不到对应元素会直接抛出异常，永远不会返回-1。你原本想判断最大值是否在队列末尾，用d.index(a)==-1的条件永远无法成立，这就是测试用例只循环一次就终止的核心原因：

• 第一次循环：队列是[4,3,1,3,4]，最大值4的索引是0，符合条件删除第一个4，队列变为[3,1,3,4]
• 第二次循环：最大值是4，index()返回3，不满足==0或==-1的条件，直接break，输出no

2. 方法调用存在冗余&潜在问题 #

每次调用max(d)、d.index(a)、d.remove(a)都是O(n)时间复杂度，且当队列中有多个相同最大值时，index()和remove()只会操作第一个出现的元素，逻辑上也没必要绕弯路查索引，直接判断队首队尾值是否等于最大值即可。

修复后代码 #

from collections import deque
T = int(input()) # 测试用例数量

for i in range(T):
    n = int(input())
    cubes = map(int, input().split())
    d = deque(cubes)       
    while len(d)!=0:
        current_max = max(d)
        # 直接判断最大值是否在两端即可
        if d[0] == current_max:
            d.popleft()
        elif d[-1] == current_max:
            d.pop()
        else:
            break
            
    if len(d)==0:
        print('yes')
    else:
        print('no')

优化建议 #

如果要进一步提升效率，可以不用每次求整个队列的最大值，而是维护上一次删除的最大值，每次仅比较队首队尾的大小，取较大的和上一次的最大值对比即可，单测试用例时间复杂度可以降到O(n)。

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