LeetCode 667. 优美的排列 II
目录
题目描述
题意分析
要造出一个由 1 到 n 各出现一次的数组，使得把所有相邻两项之差取绝对值后，去重之后剩下的取值个数恰好等于 k。答案不唯一，输出任意一个合法解即可。
「恰好 k 种」这三个字要抠清楚：不是至多 k 种，也不是最大差值为 k，而是差值集合的大小正好是 k。相邻差一共有 n - 1 个，取值只能落在 1 到 n - 1 之间，所以差值种类最多是 n - 1 种，这也解释了约束里为什么写 $1 \le k < n$——这个范围内一定有解，不需要考虑无解分支。
另一个要读出来的信号是「输出任意一个」。当一道题只要求给出一个可行解而不是最优解、也不是全部解时，正确的姿势是直接构造，而不是搜索加剪枝。n 到一万，任何指数级或平方级的做法都不用考虑。
解法：双指针构造
核心思路
暴力做法是枚举 1 到 n 的全部排列，逐个统计差值种类，命中 k 就返回。排列数是 $n!$，n 取到 10 就已经不可行，更别说一万。
瓶颈在于把「找一个解」当成了「在解空间里搜索」。既然题目允许任意解，就应该反过来问：什么样的排布方式能让差值种类可控？
从一个极端例子入手。把 1 到 n 按 1, n, 2, n-1, 3, … 的顺序左右横跳着排，相邻差依次是 $n-1, n-2, n-3, \dots$，严格递减且两两不同，恰好凑出 n - 1 种，也就是能取到的最大值。另一个极端是直接顺序排 1, 2, …, n，相邻差全是 1，只有 1 种。两个极端摆在一起，思路就出来了：把横跳的范围缩小，只对前面一小段做横跳来「造种类」，后面一整段顺序排来「不造新种类」。
具体地，只在 $[1, k+1]$ 这 k + 1 个数上横跳，写出 $1, k+1, 2, k, 3, \dots$，相邻差依次是 $k, k-1, \dots, 1$，正好 k 种且互不相同。剩下的 $k+2, k+3, \dots, n$ 直接按升序接在后面，它们内部的相邻差全是 1，而 1 已经在前段出现过（$k \ge 1$ 保证了这一点），不会引入新种类。
唯一需要验证的是两段拼接处那一个差值。设横跳段最后落下的数是 t，拼接处的差就是 $k + 2 - t$。当 k 为偶数时，最后一个位置的下标 k 是偶数，取自左指针，此时左指针已经推进了 $k/2 + 1$ 次，$t = k/2 + 1$，拼接差为 $k/2 + 1$；当 k 为奇数时，最后一个位置取自右指针，右指针推进了 $(k+1)/2$ 次，$t = (k+3)/2$，拼接差为 $(k+1)/2$。两种情形算出的拼接差都落在 1 到 k 之间，早已被前段覆盖。于是整个构造的差值集合精确等于 ${1, 2, \dots, k}$，大小正好 k。
贯穿构造过程的不变量是：写下标 idx 时，若 idx 为偶数则取当前未用的最小值，为奇数则取当前未用的最大值，且这两个值始终被 left 与 right 指向，区间 $[left, right]$ 恰好是尚未使用的数。
解题步骤
- 开一个长度为 n 的结果数组，令 left = 1、right = k + 1、idx = 0。right 取 k + 1 而不是 n，是因为横跳段只需要 k + 1 个数就能造出 k 种差值，多余的数留给后面的顺序段。
- 当
left <= right时循环填数：idx 为偶数取 left 并让 left 加一，idx 为奇数取 right 并让 right 减一，每次 idx 加一。循环条件必须带等号，两个指针相遇时那个数同样要被写入，否则会漏掉一个位置。- 循环退出时 $[1, k+1]$ 里的数已经全部用完，写出的相邻差依次是 $k, k-1, \dots, 1$，恰好 k 种。
- 把 $k+2$ 到 n 按升序依次追加。必须升序而不是降序，降序会在拼接处或段内制造出前段没有的大跨度差值。
- 返回结果数组。整个过程没有任何判定或回溯，构造即答案。
以 n = 5、k = 3走一遍：初始 left = 1、right = 4、idx = 0。idx = 0 是偶数，写入 1，left 变成 2；idx = 1 是奇数，写入 4，right 变成 3；idx = 2 是偶数，写入 2，left 变成 3；idx = 3 是奇数，此时left = 3 <= right = 3仍然成立，写入 3，right 变成 2，循环结束。此时数组是 [1, 4, 2, 3]，相邻差依次是 3、2、1，正好三种。接着追加 k + 2 = 5 到 n = 5 这一段，只有一个 5，数组变成 [1, 4, 2, 3, 5]。拼接处的差是 $3 - 5 = 2$，已经在集合里。最终相邻差序列是 3、2、1、2，去重后是 {1, 2, 3}，大小恰好等于 k = 3，构造成立。
代码实现
// 先在区间 [1, k+1] 内交替取左右端点，得到差值从 k 递减到 1。
class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
int left = 1;
int right = k + 1;
int idx = 0;
while (left <= right) {
if (idx % 2 == 0) {
res[idx++] = left++;
} else {
res[idx++] = right--;
}
}
for (int val = k + 2; val <= n; val++) {
res[idx++] = val;
}
return res;
}
}
// 先在区间 [1, k+1] 内交替取左右端点，得到差值从 k 递减到 1。
func constructArray(n int, k int) []int {
res := make([]int, n)
left := 1
right := k + 1
idx := 0
for left <= right {
if idx%2 == 0 {
res[idx] = left
left++
} else {
res[idx] = right
right--
}
idx++
}
for val := k + 2; val <= n; val++ {
res[idx] = val
idx++
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，横跳段写入 k + 1 个位置、顺序段写入 n - k - 1 个位置，合起来每个位置只被写一次，没有任何判定或回溯。
- 空间复杂度：$O(n)$，全部来自必须返回的结果数组；除去输出只用了 left、right、idx 三个整型变量，额外空间是 $O(1)$。
关键点总结
- 题面只要「任意一个可行解」时，第一反应应该是构造而不是搜索；能不能想到这一层，往往就决定了这道题是 $O(n)$ 还是 $O(n!)$。
- 构造类题目的通用切入点是先算两个极端：本题里全横跳给出 n - 1 种差值、全顺序给出 1 种差值，把两个极端拼起来就能在中间取到任意 k。
- 差值种类靠「前段横跳制造、后段顺序稀释」来精确控制，这种「一段负责造性质、一段负责不破坏性质」的分段构造思路可以迁移到大量排列构造题上。
- 构造完必须回头验证拼接处，因为两段各自的性质都成立不等于合起来成立；本题的拼接差经分类讨论恒落在 1 到 k 之间，构造才算真正闭合。
- 面试视角：面试官几乎一定会问「你怎么保证恰好是 k 种而不是 k + 1 种」，答不上来就等于没做出来。要准备好按 k 的奇偶分类，把横跳段最后一个数与 k + 2 的差算出来，说明它落在已有集合里。
- 面试视角：主动补一句「差值种类的可行范围是 1 到 n - 1，题目约束 $k < n$ 已经保证有解，所以不需要无解分支」，能表明你验算过边界而不是照抄构造。
易错点总结
- 错误写法：横跳的右端点取成 n 而不是 k + 1：
n = 5、k = 3→ 全部五个数都参与横跳，得到 [1, 5, 2, 4, 3]，差值是 4、3、2、1 共四种，比要求多了一种。- 错误写法：循环条件写成
left < right，漏掉两指针相遇的那个数：n = 3、k = 2→ 写完 1 和 3 之后 left 与 right 都等于 2，循环提前结束，最后一个位置保持默认值 0，返回 [1, 3, 0]，根本不是 1 到 n 的排列。- 错误写法：顺序段的起点写成 k + 1 而不是 k + 2：
n = 5、k = 3→ 数值 4 被写入两次而 5 从未出现，结果 [1, 4, 2, 3, 4] 有重复元素，不是合法排列。- 错误写法：顺序段改成从 n 递减追加：
n = 7、k = 2→ 得到 [1, 3, 2, 7, 6, 5, 4]，拼接处凭空多出一个差值 5，差值集合变成三种而不是要求的两种。- 错误写法：交替条件写成
left % 2 == 0之类依赖数值而非下标的判断：n = 5、k = 3→ left 一直停在 1 从不满足条件，全部从右侧取数，得到 [4, 3, 2, 1, 5]，差值只有 1 和 4 两种。- 错误写法：横跳时只在其中一个分支里推进 idx：
n = 5、k = 3→ 从右侧取的数反复覆盖同一个位置，另外一半位置保持为 0，返回的数组既有重复又有缺失。- 错误写法：把 k 理解成「相邻差的最大值不超过 k」或「至多 k 种差值」，于是直接返回 1 到 n 的顺序数组：
n = 3、k = 2→ 返回 [1, 2, 3]，差值只有 1 这一种，达不到要求的两种。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 46. 全排列 | 中等 | 要求列出所有排列，只能回溯枚举，与构造单解截然不同 |
| 31. 下一个排列 | 中等 | 在字典序上做局部调整，靠找降序断点加原地反转 |
| 60. 排列序列 | 困难 | 按阶乘进制逐位定位第 k 个排列，同为构造但依赖计数 |
| 280. 摆动排序 | 中等 | 约束的是相邻元素的大小交替关系而非差值种类 |
| 324. 摆动排序 II | 中等 | 严格不等的摆动，需要配合中位数划分与穿插下标映射 |