题意理解

一组数，找出一个合适的排序，是相邻两个数之间差的最大值要最小。注意首位两个数也是相邻的。

方法一

暴力求解。找出所有可能的排序，计算对应差值的最大值，在所有的最大值中输出最小的。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * ​返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型vector 花的高度数组
     * @return int整型
     */
    int arrangeFlowers(int n, vector<int>& array) {
        // write code here
        sort(array.begin(), array.end());
        int minm = 1e9;
        do{
            int maxm = abs(array[0] - array[n-1]);
            for (int i=1;i<n;i++)
                maxm = max(maxm, abs(array[i]-array[i-1]));
            minm = min(minm,maxm);
        }while(next_permutation(array.begin(), array.end()));//使用提供的函数生成全排列
        return minm;
    }
};

时间复杂度：$O(N!)O(N!)$O(N!)。全排列的时间复杂度是N的阶乘，这种方法超时。
空间复杂度：$O\left(1\right)O(1)$O(1)。没有开辟新的空间。

方法二

由于是一个圈，第1个数的位置无所谓。我们从第1小的数开始放。假设最优的策略为：第1小的数左侧依次为第2、4、6···小的数，右侧依次为3、5、7···小的数。

当一个排序不是之前提到的最优策略，我们一定可以通过交换两个数的位置使得最大差值变小。用ai表示第i小的数。

示意图如下：

正确性证明（反证法）：
若a1左侧是ai不是a2，则交换ai和a2。假设ai左侧的数为aj。
1）a1与其左侧相邻的数的差变小。
2）ai到新位置后与左、右数的差必小于ai和a1的差。
3）a2到新位置后，若ai小于aj，则与aj的差大于ai和aj的差。此时，aj最小是a5，而最优策略a2左侧为a4，需要继续交换。
这样可以继续推导出条件1）、2）、3），并继续交换，直到达成满足最优策略的排序。

一定要是a2,a4,a6···和a3,a5,a7···的顺序吗？
我们假设交换a4和a5。

若a2,a5,a6三者的差值变小，则a2,a4的差小于a4,a6的差；
分情况讨论：
1）原先排序中最大的差为a4,a6，则交换后a4,a7的差更大，导致最大值变大。 2）原先排序中最大的差为a3,a5，则交换后a2,a5的差更大，导致最大值变大。
3）原先排序中最大的差为a5,a7，则交换后a4,a7的差更大，导致最大值变大。

若a2,a5,a6三者的差值变大，则原先排序中最大的差为a3,a5或a5,a7的差； 分情况讨论： 1）原先排序中最大的差为a3,a5，则交换后a2,a5的差更大，导致最大值变大。
2）原先排序中最大的差为a5,a7，则交换后a4,a7的差更大，导致最大值变大。

所以交换a4和a5并不能使最大值减小，反而有可能增大最大值。

综上所述，最优策略为：第1小的数左侧依次为第2、4、6···小的数，右侧依次为3、5、7···小的数。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * ​返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型vector 花的高度数组
     * @return int整型
     */
    int arrangeFlowers(int n, vector<int>& array) {
        // write code here
        //从小到大排序
        sort(array.begin(), array.end());
        int maxm;
        //处理圈的起点和终点
        maxm = max(array[1]-array[0], array[2]-array[0]);
        maxm = max(maxm,  array[n-1]-array[n-2]);
        for (int i=3;i<n;i++)
        {
            //判断第2、4、6···以及1、3、5···小的相邻数之间的差与maxm的大小
            if (maxm<array[i]-array[i-2]) maxm = array[i] - array[i-2];
        }
        return maxm;
    }
};

时间复杂度：$O\left(NlogN\right)O(NlogN)$O(NlogN)。排序消耗的时间最多。
空间复杂度：$O\left(1\right)O(1)$O(1)。没有开辟新的空间。