如何判断列表是合法块序列：每个块首尾同值且结尾是首值的下一次出现

优化思路 #

你原实现性能较差的核心原因是Python列表的pop(0)、in成员查询、remove删除操作均为O(n)时间复杂度，嵌套循环下整体时间复杂度达到O(n²)，列表长度较大时性能会大幅下降。
我们可以通过预处理索引+单次遍历的方式把时间复杂度降到O(n)：

1. 先提前统计每个值所有出现的索引，存入队列方便快速取用
2. 用指针遍历列表，每次找到当前块开头值的下一次出现位置，直接跳到块结束位置的下一位继续处理即可

优化后代码 #

O(n)时间复杂度版本（推荐处理长列表） #

from collections import defaultdict, deque

def is_valid(lst):
    # 预处理：统计每个值的所有出现位置
    pos_map = defaultdict(deque)
    for idx, val in enumerate(lst):
        pos_map[val].append(idx)
    
    n = len(lst)
    cur_ptr = 0
    while cur_ptr < n:
        current_start_val = lst[cur_ptr]
        # 弹出所有已经处理过的过期位置
        while pos_map[current_start_val] and pos_map[current_start_val][0] <= cur_ptr:
            pos_map[current_start_val].popleft()
        # 没有找到匹配的结束值，序列非法
        if not pos_map[current_start_val]:
            return False
        # 跳到当前块结束位置的下一位
        cur_ptr = pos_map[current_start_val].popleft() + 1
    return True

# 测试用例，输出与预期完全一致
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))  # True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))  # False
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))  # True
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))  # False
print(is_valid([]))  # True

轻量无依赖版本（适合短列表） #

如果不想引入额外依赖，这个版本避免了列表修改开销，实际运行速度也远快于原实现：

def is_valid(lst):
    n = len(lst)
    cur = 0
    while cur < n:
        val = lst[cur]
        # 找cur之后第一个等于val的结束位置
        end = cur + 1
        while end < n and lst[end] != val:
            end += 1
        if end >= n:
            return False
        cur = end + 1
    return True

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