P2490. 特异性双端队列

解题思路

这道题乍一看好像需要使用队列进行模拟，但是实际上并不需要。

题意理解

首先需要理解题目含义。以题目提供的唯一示例为例，构建一个空的双端队列，我们模拟这整个过程。

本题重点就在于对 “调整” 一词的理解。可以看到，这里的调整并不是指单个元素的位置修改或者和两两元素之间的交换，而是指 对整个双端队列进行顺序打乱。

如果“调整”的含义是其他理解的话，上述例子并不能得到 1 这个结果。感兴趣的同学可以自己思考一下。

无需基于队列的模拟

容易发现，由于题目要求删除顺序是从 1 到 n，每一次出现 remove 指令的时候，我们必然要思考当前队头元素是否恰好是当前顺序里面将要被删除的元素。

而一旦需要进行调整，我们一定是 贪心地将整个队列都调整成从队头到队尾的顺序结构，这样才可以在连续出现 remove 指令的时候，不需要额外的顺序调整，也可以按照顺序继续删除。

那么什么时候，我们队列中已经调整好的顺序会被打乱？

我们进行分类讨论：

• 当我们的队列为空的时候，当前加入的元素，无论是从队头加入还是队尾加入，都会使得队列只存在一个元素，不会影响队列中的顺序。
• 当我们对一个已经调整好的队列，在队尾加入元素时，由于添加的元素总是按照大小顺序添加，因此在队尾添加 也不会影响队列中的顺序。
• 当我们对一个已经调整好的队列，在队头加入元素时，由于添加的元素总是按照大小顺序添加，因此在队头添加的这个元素会使得队列中的顺序发生改变，下次出现 `remove` 指令的时候，我们必须再次进行顺序调整。
• 当我们对一个已经是乱序需要调整的队列，无论从队头还是队尾加入元素，此时队列仍然是乱序，下次遇到 `remove` 指令的时候，我们都必须再次进行顺序调整。

所以本题 完全不需要使用一个真正的队列进行模拟，而只需要通过题目所给的指令顺序即可判断调整次数。

我们可以设置一个布尔类型变量 needModify，当其为 True 且遇到 remove 指令的时候，就需要对队列进行调整，调整次数 +1。故和调整次数更新相关的代码为：

与此同时，当队列不为空且指令为在队头添加元素时，我们需要将 needModify 修改为 False。

当 remove 指令出现的次数 removeNum（表示一共移除了 removeNum 个元素）加 1 后恰好等于下一个添加的元素数值时，此时队头为空。故可以修改代码如下：

而其他的情况都不用修改任何变量，直接不予讨论即可。至此代码就完成了。

复杂度分析 代码只有一个循环：读入并处理 2n 条指令，每条指令只做常数级操作——与 "remove" 做一次字符串比较、看首字符是否为 'h'、必要时用切片 op[9:] 取出数字并与 removeNum + 1 比较，然后更新 num、needModify、removeNum 中的某个变量。单条指令长度是固定格式、可视为常数，因此总时间复杂度为 O(n)。空间是本解法的亮点：完全没有构造真实的双端队列，只用三个标量变量记录状态，空间复杂度为 O(1)。这正是题解开头"不需要使用队列进行模拟"这一观察的收益——把一道看似要维护整个队列内容的题，压缩成了对指令流的一趟线性扫描：真正决定要不要调整的只有"队列当前是否有序"这一个布尔状态，而它只会被"非空时从队头插入"这一种事件破坏、被一次调整恢复。