最小的调整次数/特异性双端队列

题目描述

有一个特异性的双端队列, 该队列可以从头部或尾部添加数据, 但是只能从头部移出数据.

小A依次执行2n个指令往队列中添加数据和移出数据. 其中n个指令是添加数据 (可能从头部添加, 也可能从尾部添加), 依次添加1到n, n个指令是移出数据.

现在要求移除数据的顺序为1到n.

为了满足最后输出的要求, 小A可以在任何时候调整队列中数据的顺序.

请问 小A 最少需要调整几次才能够满足移除数据的顺序正好是1到n.

输入描述

• 第一行一个数据n, 表示数据的范围
• 接下来的2n行, 其中有n行为添加数据, 指令为:
• head add x表示从头部添加数据 x
• tail add x 表示从尾部添加数据x
• 另外 n 行为移出数据指令, 指令为 remove 的形式, 表示移出1个数据
• 1 ≤ n ≤ 3 * 10^5
• 所有的数据均合法

输出描述

一个整数, 表示 小A 要调整的最小次数.

示例1

输入:

5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove

输出:

1

题解

Python

from collections import deque

def main():
    # 读取输入, number 是整数n, 对队列的操作次数是 number * 2
    number = int(input())

    # 创建双端队列
    queue = deque()
    # 是否依照顺序删除
    in_order = True
    # 调整操作的次数
    adjust_times = 0

    # 遍历所有的整数, 依次检查对它的操作
    for i in range(number * 2):
        # 解析每次输入
        parts = input().split()
        op = parts[0]
        if op == "head":
            # 如果此时队列不为空, 说明这个插入导致了无序
            if len(queue) > 0:
                in_order = False
            # 从头部插入整数
            queue.appendleft(int(parts[2]))
        elif op == "tail":
            # 从尾部插入整数
            queue.append(int(parts[2]))
        elif op == "remove":
            # 如果队列为空, 忽略它
            if len(queue) == 0:
                continue
            # 如果不按顺序插入, 则需要调整一次
            if not in_order:
                adjust_times += 1
                in_order = True
            # 从头部移除整数
            queue.popleft()

        else:
            # 无效输入
            pass

    # 输出结果
    print(adjust_times)

if __name__ == "__main__":
    main()