难度: Medium
给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：
answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。
示例 1：
输入：n = 3, k = 1 输出：[1, 2, 3] 解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1
示例 2：
输入：n = 3, k = 2 输出：[1, 3, 2] 解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2
提示：
1 <= k < n <= 104
运行时间: 27 ms
内存: 16.8 MB
class Solution:
def constructArray(self, n: int, k: int) -> List[int]:
ans = [1]
op = True
for i in range(k,0,-1):
ans.append(ans[-1]+i if op else ans[-1]-i)
op ^= 1
for i in range(k+2,n+1):
ans.append(i)
return ans
该题解的核心思路是通过有规律的构造数字序列来生成一组特定的差值。初始时将1添加到答案列表中，然后交替地加上或减去从k开始递减到1的值，以此来构建k个不同的差值。具体地，初始方向为加法，之后每一步交替变换加法和减法操作。在完成这k个差值的构造后，剩余的数字从k+2到n依序加入列表尾部，这些后续添加的数字不会产生新的差值，因为它们相邻且连续，差值为1。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def constructArray(self, n: int, k: int) -> List[int]:
ans = [1] # 初始化答案数组，从1开始
op = True # 初始化操作符，True表示加法，False表示减法
for i in range(k, 0, -1): # 从k递减到1
if op:
ans.append(ans[-1] + i) # 如果是加法，当前元素等于前一个元素加i
else:
ans.append(ans[-1] - i) # 如果是减法，当前元素等于前一个元素减i
op ^= 1 # 切换操作符，True变False，False变True
for i in range(k + 2, n + 1): # 从k+2到n
ans.append(i) # 直接添加剩余的数
return ans # 返回结果
这是因为在构造k个不同差值的过程中，最后一个数字已经是k+1或者1，具体取决于添加的是正值还是负值。如果从k+1开始添加剩余的数字，将会重复使用已经在数组中的数字，导致数组中的元素不唯一，违反题目要求。因此，从k+2开始添加可以确保所有数字都是独一无二的，并且维持数组中的连续性。
交替操作加法和减法是为了创造出k个不同的差值。例如，首先从1开始，加上一个较大的数产生一个差值，然后减去一个稍小的数产生另一个不同的差值，以此类推。这种方法可以确保每次操作后的差值都是唯一的，因为加法和减法交替使用，差值的正负符号也会交替，避免重复。通过这种策略，可以精确地控制并产生k个不同的差值，满足题目的需求。
通过从k递减到1，算法确保了差值从最大可能的差值开始逐渐减小到1。这种递减顺序允许每次生成的差值都是唯一的，因为每次都是使用前一次未使用的最大差值。如果顺序相反，可能导致较小的差值先被生成，后续较大的差值因超出范围而无法实现，从而无法达到k个不同差值的目标。
如果k等于n-1，此时需要构造一个拥有n-1个不同差值的排列，这意味着数组中的每两个相邻数字的差都需要是唯一的。算法在这种情况下仍然有效，因为从1开始，通过交替加上和减去从n-1开始到1的值，可以确保生成所有从1到n-1的差值。这种情况下，不需要添加额外的数字，因为所有的数字都已经在构造k个不同差值的过程中被使用了。