P2698. 篮球游戏

解题思路

篮球只能从右边放入，但可以同时从左边和右边拿出，这显然是一个具有限制条件的双向队列。

输入的第一行为入队顺序，输入的第二行为出队顺序。

题目本质上是要求模拟整个入队、出队过程，有点类似于队列版的 验证栈序列。

入队和出队的顺序都是固定的，但是出队过程可以穿插在入队过程中。换句话说，当我们按照顺序发现下一个要出队的元素就是队头或队尾的某个元素的时候，就执行出队操作，否则继续执行入队操作。

遍历与索引设置

对于入队序列，我们可以直接使用 for 循环来进行遍历，即 for push_num in push_list。 对于出队序列，我们可以设置一个索引 pop_idx，表示当前出队序列进行到哪一个元素了。

循环中的步骤

在 for 循环下，需要做如下步骤：

1. 将当前入队元素 push_num 加入到队列中，进行队列的更新。 2. 当队列的状态发生改变之后，考虑当前队头或队尾元素是否为下一个出队元素 pop_list[pop_idx]。执行一个 while 循环，退出条件为 q 为空。若：

• 队头元素等于下一个出队元素，即 q[0] == pop_list[pop_idx]。则队列 q 弹出队头元素，同时更新 pop_idx 和 ans。
• 队尾元素等于下一个出队元素，即 q[-1] == pop_list[pop_idx]。则队列 q 弹出队尾元素，同时更新 pop_idx 和 ans。
• 否则，说明当前队头或队尾元素都不是即将弹出的元素，使用 break 直接退出当前的 while 循环。

整理为代码

复杂度分析 设篮球的个数为 n。

• 时间复杂度：O(n)。外层 for 循环把每个球恰好入队一次。内层 while 看似嵌套，但它每循环一圈必然让一个球出队（队头或队尾命中出队序列的下一个元素），否则立刻 break；而每个球最多出队一次，所以 while 在整个程序运行期间的总执行次数不超过 n，两层循环的总工作量是摊还线性的。队头 q[0]、队尾 q[-1] 的比较以及 deque 两端的弹出都是 O(1)。
• 空间复杂度：O(n)。双端队列 q 在最坏情况下（先把球全部放入、最后才开始取出）会存下全部 n 个球；答案字符串 ans 的长度也不超过 n。

瓶颈就是这一趟入队加摊还出队的扫描，没有更高阶的开销。