题目描述

n朵花排成一圈，最小化相邻两朵花高度差的最大值，输出最大值。
返回按照这些花排成一个圆的序列中最小的“丑陋度”（此句在代码注释中）

题意解析

给你一堆数字让你围成一个圆，计算圆的丑陋度，所谓丑陋度就是这个圆中相邻高度差的最大值。要求你找出所有排列可能最小的那个丑陋度。

示例

输入1：
5,[2,1,1,3,2]
返回值：1
输入2：
3,[30,10,20]
返回值：20

题解

暴力法：全排列

根据题意解析，这个题目其实就是找所有排列组合中，丑陋度最高的一个。
那暴力的办法自然就是进行全排列，然后针对每一种组合计算出其丑陋数，然后取其中最小的。
代码如下：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * ​返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型一维数组 花的高度数组
     * @return int整型
     */
    // 初始化为Integer.MAX_VALUE，因为花的高度范围是小于MAX_VALUE的，所以设置这个值是合理的
    public static int minUgly = Integer.MAX_VALUE;
    public int arrangeFlowers (int n, int[] array) {
        perm(array,0,array.length-1);
        return minUgly;
    }
    // 全排列递归写法
    public static void perm(int[] array,int start,int end) {
        if(start==end) {
            // 此时形成了一种全排列的可能，计算该种排列的丑陋数并与现有最小值比较，取更小的
            minUgly = Math.min(minUgly,helper(array));
        } else {
            for (int i = start; i <= end; i++) {
                swap(array,start,i);
                // 递归确定start+1位置的数值
                perm(array,start+1,end);
                // 将交换还原
                swap(array,start,i);
            }
        }
    }
    // 交换 i,j位置的数字
    public static void swap(int[] array,int i,int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    // 计算当前排列下的丑陋度
    public static int helper(int[] array) {
        //初始化为收尾的差的绝对值
        int max = Math.abs(array[0]-array[array.length-1]);
        for(int i=1;i<array.length;i++){
            // 丑陋度 = max（高度差）
            max = Math.max(max,Math.abs(array[i]-array[i-1]));
        }
        return max;
    }
}

该解法很明显在题目描述的数据范围下会出现超时情况。
因为该解法的时间复杂度为，因为n个数字的全排列有种可能，空间复杂度为

寻找更优解

首先，我们假设现在不是一个圈，只是一条线，请问这个问题如何解决？
很简单，对这组数进行排序，然后找到其中相邻高度差最大的值就是解。

那现在围成一个圆呢？
围城圆之后由于首尾的差就要被计算了，所以刚刚的方法就不行了。

我发现这个问题不能靠想的，要具体动手去试，才能找到思路。
当只有1个数和2个数的时候，只有一种摆法，我们从3个说起
假设当前有3个，高度从小到大依次是a、b、c,
此时高度差最大肯定是c和a，但是无论哪一种摆法，ca肯定都会相邻，所以此时随便哪种都是一样的结果；

那如果是4个呢？分别高度从小到大依次为 a,b,c,d
我们是有办法避开最大的高度差a和d的。
于是我们现从大到小取出d，（也可以从小到大取），此时剩下的abc要选择2个放到d的旁边，应该取bc，因为a和d的高度差最大，肯定不能连着放。最后剩下a，任意放在一遍都可以，因为这两种情况下的结果是一样的，如下图所示：

继续考虑5个，分别从小到大为 a,b,c,d,e，当确定的最大值e以及最大值两侧c、d后，来到一个选择，可能得答案只有两种，分别如下图所示：

图中上面和下面两种可能得情况中，
由于上面的情况中存在 这个可能得最大值，而这个最大值是肯定大于下面那种情况的（圈红的部分），所以下面的才是最优解。

依次类推：我们发现，如果有n个数的排列，最优解其实是按照顺序分布在两边的，且依次相隔2个位置
所以，n个数的有序数列，其最优解的序列为
按照这个思路写代码，就简单很多了

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * ​返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型一维数组 花的高度数组
     * @return int整型
     */
    public int arrangeFlowers (int n, int[] array) {
        Arrays.sort(array);
        //因为按照我们刚刚的思路，第一和第二小的数肯定是会被分到2边的，所以围成圆的话，其高度差肯定是一个可能的结果，所以以它作为一个初始值是合理的
        int ans = array[1] - array[0];
        // 依次比较2个身位差之间数字的差值，由于已经排序所以不需要考虑绝对值问题
        for(int i = 2 ; i < n ; i++){
            ans = Math.max(ans , array[i] - array[i - 2]);
        }
        return ans;
    }
}

细心的同学应该会发现，在上面推理的时候会发现挡奇数个数的时候（如上面5个数的时候），可能得结果中其实是存在一种可能是的，但是实际算法中只计算了array[i] - array[i - 2] 相邻两个身位的数值差，会不会有问题呢？ 其实这样是没问题的，因为在奇数个的时候其答案中既存在也存在，由于有序性，所以是肯定要大于的，而丑陋数是差的最大值，所以在这种情况下不可能是丑陋数，所以不需要考虑。

该解法的时间复杂度为 ，因为其中有排序操作
空间复杂度为