幼儿园里有一个放倒的圆桶,它是一个线性结构,允许在桶的右边将篮球放入,可以在桶的左边和右边将篮球取出。每个篮球有单独的编号,老师可以连续放入一个或多个篮球,小朋友可以在桶左边或右边将篮球取出,当桶只有一个篮球的情况下,必须从左边取出。
给定老师放入篮球的顺序和小朋友取出篮球的顺序,判断取出顺序是否可行。如果可行,输出相应的取出操作序列(用L
表示从左取,R
表示从右取);否则,输出NO
。
这个问题可以使用双端队列(deque)来模拟桶的操作过程。具体步骤如下:
幼儿园里有一个放倒的圆桶,它是一个线性结构,允许在桶的右边将篮球放入,可以在桶的左边和右边将篮球取出。
每个篮球有单独的编号,老师可以连续放入一个或多个篮球,小朋友可以在桶左边或右边将篮球取出,当桶只有一个篮球的情况下,必须从左边取出。
如老师按顺序放入1、2、3、4、5共有 5 个编号的篮球,那么小朋友可以依次取出编号为 1、2、3、4、5 或者 3、1、2、4、5 编号的篮球,无法取出 5、1、3、2、4 编号的篮球。
其中 3、1、2、4、5 的取出场景为:
简答起见,我们以 L 表示左,R 表示右,此时取出篮球的依次取出序列为“RLLLL”。
每次输入包含一个测试用例:
其中篮球编号用逗号进行分隔。
对于每个篮球的取出序列,如果确实可以获取,请打印出其按照左右方向的操作取出顺序,如果无法获取则打印“NO”。
输入
4,5,6,7,0,1,2
6,4,0,1,2,5,7
输出
RLRRRLL
说明
篮球的取出顺序依次为“右、左、右、右、右、左、左”
输入
4,5,6,7,0,1,2
6,0,5,1,2,4,7
输出
NO
说明
无法取出对应序列的篮球
输入
1,2,3,4
1,2,3,5
输出
NO
说明
不存在编号为 5 的篮球,所以无法取出对应编号的数据