构建字典序最大的可行序列

难度: Medium

给你一个整数 n ，请你找到满足下面条件的一个序列：

整数 1 在序列中只出现一次。
2 到 n 之间每个整数都恰好出现两次。
对于每个 2 到 n 之间的整数 i ，两个 i 之间出现的距离恰好为 i 。

序列里面两个数 a[i] 和 a[j] 之间的距离，我们定义为它们下标绝对值之差 |j - i| 。

请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下，一定存在解。

一个序列 a 被认为比序列 b （两者长度相同）字典序更大的条件是： a 和 b 中第一个不一样的数字处，a 序列的数字比 b 序列的数字大。比方说，[0,1,9,0] 比 [0,1,5,6] 字典序更大，因为第一个不同的位置是第三个数字，且 9 比 5 大。

示例 1：

输入：n = 3
输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。

示例 2：

输入：n = 5
输出：[5,3,1,4,3,5,2,4,2]

提示：

1 <= n <= 20

Submission

运行时间: 28 ms

内存: 16.4 MB

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        res = [None] * ((n << 1) - 1)
        # info = { 1 : 1}
        # for i in range(2, n + 1):
        #     info[i] = 2
        visited = set()
        self.recurse(res, n, 0, 1, visited)
        return res
    
    def recurse(self, res, n, idx, t, visited):
        # if t == n:
        #     return True

        # visited = set()
        next_idx = None
        for i in range(n, 0, -1):
            if i in visited:
                continue
            
            if i > 1 and idx + i >= len(res):
                continue
            
            if i > 1 and res[idx + i] is not None:
                continue
            
            visited.add(i)
            res[idx] = i 
            if i > 1:
                res[idx + i] = i 
            
            if t == n:
                return True
            
            next_idx = idx + 1
            while res[next_idx] is not None:
                next_idx += 1
            
            if self.recurse(res, n, next_idx, t + 1, visited):
                return True
            
            if i > 1:
                res[idx + i] = None
            res[idx] = None
            visited.remove(i)

Explain

此题解基于回溯算法。首先，初始化一个长度为2n-1的数组res，用于存放最终的序列。数组中的每个位置初始值为None，表示尚未放置任何数字。使用一个集合visited来记录当前已经被放置在序列中的数字。回溯函数recurse通过递归的方式尝试在序列res中放置数字，从n开始尝试到1，以确保字典序最大。对于每个数字i，如果i未被访问过，并且位置上的放置是可行的（对于大于1的i，需要确保res[idx + i]也未被占用），则将i放入当前位置和对应的间隔位置（如果i大于1）。然后，继续递归尝试填充下一个位置。如果递归成功，返回True；否则，撤销当前放置，尝试下一个数字。通过这种方式，算法尝试构建字典序最大的序列。

时间复杂度: O(n!)

空间复杂度: O(n)

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        res = [None] * ((n << 1) - 1) # 初始化结果数组，长度为2n-1
        visited = set() # 访问标记集合
        self.recurse(res, n, 0, 1, visited)
        return res
    
    def recurse(self, res, n, idx, t, visited):
        for i in range(n, 0, -1): # 从大到小尝试放置数字以保证字典序最大
            if i in visited: # 如果数字已被使用则跳过
                continue
            if i > 1 and idx + i >= len(res): # 确保不会越界
                continue
            if i > 1 and res[idx + i] is not None: # 确保间隔位置未被占用
                continue
            visited.add(i) # 标记数字为已使用
            res[idx] = i # 放置数字
            if i > 1:
                res[idx + i] = i # 放置间隔数字
            if t == n: # 如果所有数字都已放置
                return True
            next_idx = idx + 1
            while res[next_idx] is not None: # 寻找下一个空位置
                next_idx += 1
            if self.recurse(res, n, next_idx, t + 1, visited): # 递归放置下一个数字
                return True
            if i > 1:
                res[idx + i] = None # 撤销间隔位置的放置
            res[idx] = None # 撤销当前位置的放置
            visited.remove(i) # 取消标记

Explore

在递归函数中从数字n开始递减尝试放置而不是从1开始，是因为我们需要构建一个字典序最大的序列。字典序比较是从左到右比较数字的大小，因此首先尝试放置较大的数可以更有可能在序列的前面放置大数字，从而确保生成的序列在字典序上尽可能大。

在回溯算法中，如果试图放置数字i后未能成功构建整个序列，需要撤销当前位置和间隔位置的放置是因为这样的放置可能阻碍了其他可能的数字放置，导致无法找到一个成功的完整序列。撤销放置允许算法回退到前一个状态，尝试其他数字的放置，从而找到正确的序列配置。

确实存在更高效的方法来确定下一个未被占用的位置，比如使用一个辅助数据结构（如队列或链表）来跟踪还未被填充的位置。每次填充位置后，可以从这个数据结构中移除相应的位置，从而快速获取下一个空位置。这种方法可以减少不必要的遍历，提高算法的效率。

构建字典序最大的序列的关键在于优先放置较大的数字，并尽可能地将这些数字放在序列的前面位置。算法从n开始递减尝试放置数字，确保一旦较大的数字可以放置，它们会立即被放置在可用的最前端位置。这样，较大的数字较早出现在序列中，从而确保整个序列的字典序尽可能大。此外，通过正确管理数字的放置和撤销（回溯），算法能够探索所有可能的配置，从而找到字典序最大的序列。