题目

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

思路

昨天每日一题1718. 构建字典序最大的可行序列 - 图1就是字典序，今天随机一题居然还是哈哈。

一看这数据量就是暴力枚举了。

一开始走了弯路，思路有些偏差：一开始以为，因为要返回字典序最大的，那么可以从最大的数1718. 构建字典序最大的可行序列 - 图2开始找坑填，从第一位开始查找可以填的位置，如果在某一位置1718. 构建字典序最大的可行序列 - 图3有：1718. 构建字典序最大的可行序列 - 图4和1718. 构建字典序最大的可行序列 - 图5都未被占用（前提是1718. 构建字典序最大的可行序列 - 图6不为1718. 构建字典序最大的可行序列 - 图7，1718. 构建字典序最大的可行序列 - 图8为1718. 构建字典序最大的可行序列 - 图9单独讨论即可），那么这两个位置可以填上1718. 构建字典序最大的可行序列 - 图10，接着1718. 构建字典序最大的可行序列 - 图11递减，依次从头查找可以安放的位置，直到1718. 构建字典序最大的可行序列 - 图12也被安放完毕。但是，这个思路是错的…输入1718. 构建字典序最大的可行序列 - 图13为1718. 构建字典序最大的可行序列 - 图14时，会得到1718. 构建字典序最大的可行序列 - 图15，而不是预期的1718. 构建字典序最大的可行序列 - 图16。一看，确实不能这么做，第一个1718. 构建字典序最大的可行序列 - 图17被放在了第三位，但是却比放在第四位的方案字典序更小。看来要转变思路。

看这个出错的用例，发现我们要确保高位的数字尽可能大，那么我们应该“优先用大的数字填高位(填高位是重点，即高位填好再填低位)”，而不是“优先填好大的数字(而不管它被放在哪里)”。这一点想清楚了，那么代码就好写了。整体是一个回溯的框架，具体实现见代码注释。这道题写了很久，注释也写的详细一点吧。

代码

  1. class Solution {
  2.     int[] ans;
  3.     // 标记是否找到一个解了
  4.     boolean flag = false;
  5.     public int[] constructDistancedSequence(int n) {
  6.         // 除了1出现1次，2到n出现两次，那么返回数组的长度为2n-1
  7.         ans = new int[2 * n - 1];
  8.         // 和ans等长，用于记录当前遍历的一个序列
  9.         int[] arr = new int[2 * n - 1];
  10.         // 初始为-1，表示这个位置没有被用过
  11.         Arrays.fill(arr, -1);
  12.         // 记录1到n各自是否已经填好了
  13.         boolean[] visited = new boolean[n + 1];
  14.         // 第二个参数0表示先填第一位，优先使用大数填
  15.         dfs(n, 0, arr, visited);
  16.         // 注意最后不能返回arr，arr元素最后都会被重置为-1，所以要多创建一个ans变量
  17.         return ans;
  18.     }
  20.     // 当前在填arr[index]
  21.     private void dfs(int n, int index, int[] arr, boolean[] visited) {
  22.         // 找到一个解了，就不再递归，因为按我们的思路，第一个解一定是字典序最大的
  23.         // 注意，这里flag是必须的，不然会遍历完所有状态，ans就是字典序最小的了
  24.         if (flag) {
  25.             return;
  26.         }
  27.         // arr所有位置都填好了
  28.         if (index == 2 * n - 1) {
  29.             flag = true;
  30.             // 将arr复制到ans，更新ans
  31.             System.arraycopy(arr, 0, ans, 0, 2 * n - 1);
  32.             return;
  33.         }
  34.         // 当前位置index已经填好了，那么就看下一位置
  35.         if (arr[index] != -1) {
  36.             dfs(n, index + 1, arr, visited);
  37.             return;
  38.         }
  39.         // 当前位置index还没填，从n开始递减地看能不能填
  40.         for (int i = n; i >= 1; i--) {
  41.             // i已经用过了，继续看i-1
  42.             if (visited[i]) {
  43.                 continue;
  44.             }
  45.             // 到这里表示i没用过，分情况讨论i是不是1
  46.             if (i == 1) {
  47.                 // 如果i是1，只需要将arr[index]赋值为i(即1)
  48.                 arr[index] = 1;
  49.                 visited[i] = true;
  50.                 dfs(n, index + 1, arr, visited);
  51.                 arr[index] = -1;
  52.                 visited[i] = false;
  53.             } else {
  54.                 // 如果i不是1，需要将arr[index+i]也赋值为i
  55.                 // 当然，如果这里arr[index + i] == -1不成立的话，说明i还是不能放在这里，需要继续循环看i-1
  56.                 if (index + i < 2 * n - 1 && arr[index + i] == -1) {
  57.                     // 到了这里说明i可以放在index和index+i处
  58.                     arr[index] = i;
  59.                     arr[index + i] = i;
  60.                     // 标记i已经填好了
  61.                     visited[i] = true;
  62.                     // 递归
  63.                     dfs(n, index + 1, arr, visited);
  64.                     // 状态重置
  65.                     arr[index] = -1;
  66.                     arr[index + i] = -1;
  67.                     visited[i] = false;
  68.                 }
  69.             }
  70.         }
  71.     }
  72. }