LeetCode 667. 优美的排列 II

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
数组 数学

题目描述

✅ 667. 优美的排列 II

image-20260928224443570

题意分析

将 1 到 n 各使用一次，构造一个排列，使相邻元素绝对差的不同取值恰好有 k 种。重复出现同一个差值只算一种；题目保证 1 <= k < n，返回任意合法排列即可。

解法：双指针构造

核心思路

[!blue]

如果一直顺序排列，相邻差都为 1。要主动制造 k 种差值，可以先处理连续的 k + 1 个数：在区间 [1, k + 1] 内交替取最左端、最右端，形成 1, k + 1, 2, k, ...。

第一次跨越两端的距离是 k。每取走一个端点，下一次从另一端取数时，跨越距离就减少 1，直到最后两个数相差 1。因此前段的 k 个相邻差恰好是 k, k - 1, ..., 1，已经包含需要的全部差值。

剩余的 k + 2 到 n 按升序追加，它们内部的差都为 1，不会引入新种类。还要检查两段的连接处：若 k = 2t，前段末值为 t + 1；若 k = 2t + 1，末值为 t + 2。接到 k + 2 时，两种情况下的差都是 t + 1，即 floor(k / 2) + 1，仍在 1 到 k 之间。

两个指针只取尚未使用的端点，前段每个数恰好使用一次；后段使用其余更大的数。因此最终既是 1 到 n 的排列，又恰好具有 k 种差值。

解题步骤

  1. 初始化 left = 1、right = k + 1 和输出位置 idx = 0。
  2. 当 left <= right 时，输出位置为偶数就取左端并右移左指针，为奇数就取右端并左移右指针。
  3. 两指针相遇时也要取走最后一个数；前段用完后，依次追加 k + 2 到 n。
  4. 返回构造出的排列。

k = 1 时整个结果就是升序排列；k = n - 1 时前段已经包含所有数，不存在连接后段的问题。

代码实现

// 先在区间 [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;

        // 两端交替取值，形成从 k 递减到一的相邻差
        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

    // 两端交替取值，形成从 k 递减到一的相邻差
    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)$，每个输出位置写入一次。
  • 空间复杂度：除返回数组 $O(n)$ 外，辅助空间 $O(1)$。

关键点总结

[!green]

  • 要制造 k 个不同相邻差，前段需要 k + 1 个数。
  • 交替取两端，让差值逐次减少，完整得到 1 到 k。
  • 后段内部和两段连接处都只复用前段已有差值，才能保证种类不会超过 k。

易错点总结

[!yellow]

  • 对整个 [1, n] 都交替取两端，会产生 n - 1 种差值，不能适配一般的 k。
  • 循环条件写成 left < right 会漏掉最后剩下的一个数。
  • 只证明前段有 k 种差值还不够，必须检查后段及连接处是否新增差值。
  • 本实现应升序追加剩余数字，随意改变顺序可能破坏已经确定的差值集合。

相似题目

题目 难度 关联与区别
942. 增减字符串匹配 简单 都从未使用数的最小或最大端取值构造排列；942 按增减关系选端点，本题交替取端点产生不同差值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/85416012
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！