蓝桥杯 消除游戏

题目位置
主要需要用到模拟链表。做法是先整体扫一遍，将要删除的位置存下来。
然后在删除这些位置的过程中，判断该位置的左右是否需要在下一轮删除，如果需要，就存下来。
这样循环，直到没有位置需要删除。细节看代码

N = int(1e6) + 10
pre = [i-1 for i in range(N)]
nxt = [i+1 for i in range(N)]
dead = [False for i in range(N)]
n, s, vec = 0, "", []

def delete(pos):
    pre[nxt[pos]], nxt[pre[pos]] = pre[pos], nxt[pos]
    dead[pos] = True

def prints():
    if nxt[0] > n: print('EMPTY')
    else:
        i = nxt[0]
        while i <= n:
            print(s[i], end='')
            i = nxt[i]
        print()

def check(pos):
    posl, posr = pre[pos], nxt[pos]
    if posl < 1 or posr > n: return
    if s[posl] != s[pos] and s[pos] == s[posr]: vec.append(posl); vec.append(pos)
    if s[posl] == s[pos] and s[pos] != s[posr]: vec.append(pos); vec.append(posr)

def main():
    global s, n
    s = input()
    n = len(s)
    s = '#' + s
    for i in range(1, n + 1): check(i)
    i = 0
    while i < len(vec):
        p = []
        while i < len(vec):
            if not dead[vec[i]]:
                delete(vec[i])
                if vec[i] > 1: p.append(pre[vec[i]])
                if vec[i] < n: p.append(nxt[vec[i]])
            i += 1
    
        for j in p:
            if not dead[j]:
                check(j)
    prints()

if __name__ == '__main__':
    main()