LeetCode 667. 优美的排列 II

Categories:

题目描述
思路分析
1. 解法一：双指针构造（推荐）
相似题目

题目描述

✅ 667. 优美的排列 II

思路分析

解法一：双指针构造（推荐）

核心思路：

目标是构造恰好 k 种不同相邻差值。

先在区间 [1, k+1] 内交替取左右端点，得到差值从 k 递减到 1。

剩余部分按递增顺序追加，不会引入新的差值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(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;
    }
}

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
}

相似题目

题目	难度	考察点
46. 全排列	中等	构造
60. 排列序列	困难	构造
484. 寻找排列	中等	构造
769. 最多能完成排序的块	中等	贪心
2149. 按符号重排数组	中等	构造

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/85416012