题意理解

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

方法一

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

具体代码如下:

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(1)O(1)O(1)。没有开辟新的空间。

方法二

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

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

示意图如下: alt

正确性证明(反证法):
若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(NlogN)O(NlogN)O(NlogN)。排序消耗的时间最多。
空间复杂度:O(1)O(1)O(1)。没有开辟新的空间。