题目分析

本题思路很重要，说实话我当时没做出来，花了5分钟，一点头绪也没有。然后看了答案，看了一下思想，就觉得豁然开朗。小伙伴们也可以花5分钟想一下，看看是否有思路呢？

数学

因为是从1-n的n个数字，我们发现如果按照从1往上递增排列，1、2、3…，那么他们之间的差值始终为1。

如果大小交错排列，1，n，2，n-1…，那么他们之间的差值为n-1，n-2，n-3…1，会有n-1个不同的情况。

因此我们只要部分有序，其他的交错，就可以做到k种不同的结果。

如果前面是1，2，3…x，后面是n，x+1，n-2…，后面的元素是从x + 1到n，一共n - x个，因此差值是n - x - 1，n - x - 2…1，加上前面x与n的差值n - x，因此差值有n - x种，前面的差值都是1，和最后一位重复了。

所以可以得出结论，我们要使差值有k种，就要让n - x = k，所以x = n - k。所以前面要从1递增到n - k，然后交叉放入最大值和最小值即可。

代码实现让left表示左边的最小值，right表示右边的最大值。先遍历n - k，让结果数组保存1，2，3…n - k，然后令一个bool变量表示当前应该放入最小值还是最大值。代码中命名为isRight，如果为true，表示应该放入right值，并将right–。然后将bool取反，放入left值，并将left++。

算法的**时间复杂度为O(n)，空间复杂度为O(1)**。

class Solution {
    public int[] constructArray(int n, int k) {
        int[] res = new int[n];
        int idx = 0;
        int left = n - k + 1;
        for (int i = 1; i < left; i++) {
            res[idx++] = i;
        }
        boolean isRight = true;
        int right = n;
        while (left <= right) {
            res[idx++] = isRight ? right-- : left++;
            isRight = !isRight;
        }
        return res;
    }
}

刷题总结

代码很神奇吧，有时候就是一个思路的问题，小伙伴们要多见见题目，以后遇到才能举一反三。