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

🟠 🔖 数组 回溯 🔗 力扣open in new window LeetCodeopen in new window

题目

Given an integer n, find a sequence that satisfies all of the following:

The integer 1 occurs once in the sequence.
Each integer between 2 and n occurs twice in the sequence.
For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return thelexicographically largest sequence . It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

Constraints:

1 <= n <= 20

题目大意

给你一个整数 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

解题思路

由于 res 的位置需要满足一定的间隔关系，因此可以采用回溯（Backtracking）+ 剪枝的策略来构造数组。

回溯框架

使用递归方法 backtrack(idx)，从索引 idx = 0 开始，尝试在 res 中填入 n 到 1，直到数组填满。

回溯细节

在 idx 位置尝试放置数字 num（从 n 递减到 1）：

跳过已填充的位置：如果 res[idx] 已有值，直接递归到下一个索引。
检查 num 是否可以放置：
- num 需要占据 idx 和 idx + num 两个位置。
- idx + num 不能超出 res 数组范围。
- idx + num 位置必须是空的。
- 特殊情况：num == 1 只占据一个位置。
放置 num，然后递归继续：
- 标记 used[num] = true，填充 res[idx] = res[idx + num] = num。
- 递归调用 backtrack(idx + 1)。
- 如果找到解，返回 true。
- 回溯（撤销选择）：如果递归失败，则撤销填充，并继续尝试更小的 num。

剪枝优化

按 n → 1 递减放置：优先尝试较大的 num，保证字典序最大。
跳过已填充的位置：if (res[idx] !== 0) backtrack(idx + 1) 避免重复计算。
提前终止无效路径：
- if (used[num]) continue：避免重复放置 num。
- if (next >= len || res[next] !== 0) continue：避免超出范围或覆盖已填充位置。

复杂度分析

时间复杂度：O(n * n!)
- 由于 res 长度为 2n - 1，理论上我们可能尝试 O(n!) 种排列方式。
- 但由于剪枝优化，实际情况远低于 O(n!)。
- 近似时间复杂度可以认为是 O(n * n!) 级别。
空间复杂度：O(n)。
- 主要由 res（O(2n-1) ≈ O(n)）和 used（O(n)）数组组成，共 O(n) 额外空间。
- 递归调用栈最深 O(n)
- 因此总空间复杂度为 O(n)。

代码

/**
 * @param {number} n
 * @return {number[]}
 */
var constructDistancedSequence = function (n) {
	const len = 2 * n - 1;
	let res = new Array(len).fill(0);
	let used = new Array(n + 1).fill(false);
	const backtrack = (idx) => {
		if (idx == len) {
			return true;
		}
		if (res[idx] !== 0) {
			return backtrack(idx + 1);
		}

		// 尝试在 res 中填入 n 到 1
		for (let num = n; num > 0; num--) {
			// 剪枝
			if (used[num]) {
				continue;
			}
			const next = num == 1 ? idx : num + idx;
			if (next >= len || res[next] !== 0) {
				continue;
			}

			// 放置 num
			res[idx] = res[next] = num;
			used[num] = true;

			// 递归
			if (backtrack(idx + 1)) {
				return true;
			}

			// 回溯
			res[idx] = res[next] = 0;
			used[num] = false;
		}
		return false;
	};
	backtrack(0);
	return res;
};

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

# 1718. 构建字典序最大的可行序列

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目