1718-构建字典序最大的可行序列

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

思路

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

一开始走了弯路，思路有些偏差：一开始以为，因为要返回字典序最大的，那么可以从最大的数n开始找坑填，从第一位开始查找可以填的位置，如果在某一位置i有：arr[i]和arr[i+n]都未被占用（前提是n不为1，n为1单独讨论即可），那么这两个位置可以填上n，接着n递减，依次从头查找可以安放的位置，直到1也被安放完毕。但是，这个思路是错的…输入n为5时，会得到[5, 2, 4, 2, 3, 5, 4, 3, 1]，而不是预期的[5,3,1,4,3,5,2,4,2]。一看，确实不能这么做，第一个4被放在了第三位，但是却比放在第四位的方案字典序更小。看来要转变思路。

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

代码

class Solution {
    int[] ans;
    // 标记是否找到一个解了
    boolean flag = false;
    public int[] constructDistancedSequence(int n) {
        // 除了1出现1次，2到n出现两次，那么返回数组的长度为2n-1
        ans = new int[2 * n - 1];
        // 和ans等长，用于记录当前遍历的一个序列
        int[] arr = new int[2 * n - 1];
        // 初始为-1，表示这个位置没有被用过
        Arrays.fill(arr, -1);
        // 记录1到n各自是否已经填好了
        boolean[] visited = new boolean[n + 1];
        // 第二个参数0表示先填第一位，优先使用大数填
        dfs(n, 0, arr, visited);
        // 注意最后不能返回arr，arr元素最后都会被重置为-1，所以要多创建一个ans变量
        return ans;
    }

    // 当前在填arr[index]
    private void dfs(int n, int index, int[] arr, boolean[] visited) {
        // 找到一个解了，就不再递归，因为按我们的思路，第一个解一定是字典序最大的
        // 注意，这里flag是必须的，不然会遍历完所有状态，ans就是字典序最小的了
        if (flag) {
            return;
        }
        // arr所有位置都填好了
        if (index == 2 * n - 1) {
            flag = true;
            // 将arr复制到ans，更新ans
            System.arraycopy(arr, 0, ans, 0, 2 * n - 1);
            return;
        }
        // 当前位置index已经填好了，那么就看下一位置
        if (arr[index] != -1) {
            dfs(n, index + 1, arr, visited);
            return;
        }
        // 当前位置index还没填，从n开始递减地看能不能填
        for (int i = n; i >= 1; i--) {
            // i已经用过了，继续看i-1
            if (visited[i]) {
                continue;
            }
            // 到这里表示i没用过，分情况讨论i是不是1
            if (i == 1) {
                // 如果i是1，只需要将arr[index]赋值为i(即1)
                arr[index] = 1;
                visited[i] = true;
                dfs(n, index + 1, arr, visited);
                arr[index] = -1;
                visited[i] = false;
            } else {
                // 如果i不是1，需要将arr[index+i]也赋值为i
                // 当然，如果这里arr[index + i] == -1不成立的话，说明i还是不能放在这里，需要继续循环看i-1
                if (index + i < 2 * n - 1 && arr[index + i] == -1) {
                    // 到了这里说明i可以放在index和index+i处
                    arr[index] = i;
                    arr[index + i] = i;
                    // 标记i已经填好了
                    visited[i] = true;
                    // 递归
                    dfs(n, index + 1, arr, visited);
                    // 状态重置
                    arr[index] = -1;
                    arr[index + i] = -1;
                    visited[i] = false;
                }
            }
        }
    }
}