题解

思路

若字典序最小的排列 $P$ 的一对相邻位置满足 $P_{2i-1}>P_{2i}$，那么这两个下标对应的字符只能依次为左括号、右括号；否则交换或提前选择更小下标会得到更小的合法排列。

做法

对字典序最大的排列同理，当 $Q_{2i-1}<Q_{2i}$ 时也能确定这两个字符。把两类限制合并，若发生冲突，或仍有字符不能确定，或左右括号数量不是各 $N$ 个，就不存在答案；这是因为未确定字符至少给出两种候选，而同一对最小、最大排列至多对应一个括号列。

得到唯一候选后，再分别模拟字典序最小和最大的合法取法：当前余额为零时必须选尚未使用的左括号下标，否则可选尚未使用的最小或最大下标。用有序集合维护所有剩余下标和剩余左括号下标，重建出的两个排列恰为 $P,Q$ 时输出候选，否则输出 -1。

复杂度

时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。